Problem Statement
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
source: leetcode image
Example 1:
Input: digits = “23”
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = “”
Output: []
Example 3:
Input: digits = “2”
Output: ["a","b","c"]
Constraints
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Approach
- Mapping digits → letters (like on a phone keypad).
- Use backtracking to build all possible strings:
At each digit, try every possible letter.Add the letterto the current path, recurse for the next digit.- When the
path lengthequals the number of digits → add to result.
- Return the collected
results.
Time Complexity
Time Complexity = O(3N * 4M)
Space Complexity
Space Complexity = O(N) (output) + O(n) (stack)
Dry Run
Input:
k = 3, n = 7
State Transitions:
Initialize: result = []Call backtrack(7, [], 1) Loop i = 1 path.push(1) → path = [1] Call backtrack(6, [1], 2) Loop i = 2 path.push(2) → path = [1, 2] Call backtrack(4, [1, 2], 3) Loop i = 3 path.push(3) → path = [1, 2, 3] Call backtrack(1, [1, 2, 3], 4) path.length == 3 but remainingSum = 1 ≠ 0 → return path.pop() → path = [1, 2] Loop i = 4 path.push(4) → path = [1, 2, 4] Call backtrack(0, [1, 2, 4], 5) path.length == 3 and remainingSum == 0 → result.push([1, 2, 4]) path.pop() → path = [1, 2] Loop i = 5 → path would be length 3 but remainingSum < 0 → return ... End inner loop path.pop() → path = [1] Loop i = 3 path.push(3) → path = [1, 3] Call backtrack(3, [1, 3], 4) Loop i = 4 path.push(4) → path = [1, 3, 4] Call backtrack(-1, [1, 3, 4], 5) remainingSum < 0 → return path.pop() → path = [1, 3] End path.pop() → path = [1] Loop i = 4 path.push(4) → path = [1, 4] Call backtrack(2, [1, 4], 5) Loop i = 5 path.push(5) → path = [1, 4, 5] Call backtrack(-3, [1, 4, 5], 6) → return path.pop() End path.pop() → path = [1] ... continue similarly path.pop() → path = [] Loop i = 2 path.push(2) → path = [2] Call backtrack(5, [2], 3) Loop i = 3 path.push(3) → path = [2, 3] Call backtrack(2, [2, 3], 4) Loop i = 4 path.push(4) → path = [2, 3, 4] Call backtrack(-2, [2, 3, 4], 5) remainingSum < 0 → return path.pop() End path.pop() → path = [2] Loop i = 4 path.push(4) → path = [2, 4] Call backtrack(1, [2, 4], 5) Loop i = 5 path.push(5) → path = [2, 4, 5] Call backtrack(-4, [2, 4, 5], 6) → return path.pop() End path.pop() End path.pop() → path = [] Loop i = 3, 4, 5... → no valid 3-number combos left within sum = 7Final Output:
[[1, 2, 4]]
var letterCombinations = function(digits) {
if(!digits.length) return [];
let letters = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
let result = [];
let backtrack = (path, index) => {
if(index === digits.length) {
result.push(path.join(""));
return;
}
let choices = letters[digits[index]];
for(let i=0; i < choices.length; i++){
path.push(choices[i]);
backtrack(path, index + 1);
path.pop();
}
}
backtrack([], 0);
return result;
};
def letterCombinations(digits: str):
if not digits:
return []
letters = {
"2":"abc", "3":"def", "4":"ghi", "5":"jkl",
"6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"
}
result = []
def backtrack(path, index):
if index == len(digits):
result.append("".join(path))
return
for ch in letters[digits[index]]:
path.append(ch)
backtrack(path, index+1)
path.pop()
backtrack([], 0)
return result
print(letterCombinations("23"))
print(sol.combinationSum3(3, 7))
import java.util.*;
class Solution {
Map letters = new HashMap<>() {{
put('2',"abc"); put('3',"def"); put('4',"ghi"); put('5',"jkl");
put('6',"mno"); put('7',"pqrs"); put('8',"tuv"); put('9',"wxyz");
}};
public List letterCombinations(String digits) {
List result = new ArrayList<>();
if(digits.isEmpty()) return result;
backtrack(new StringBuilder(), 0, digits, result);
return result;
}
private void backtrack(StringBuilder path, int index, String digits, List result) {
if(index == digits.length()) {
result.add(path.toString());
return;
}
String choices = letters.get(digits.charAt(index));
for(char c : choices.toCharArray()) {
path.append(c);
backtrack(path, index+1, digits, result);
path.deleteCharAt(path.length()-1);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.letterCombinations("23"));
}
}
class Solution {
public:
vector letterCombinations(string digits) {
if(digits.empty()) return {};
unordered_map letters = {
{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
{'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}
};
vector result;
string path;
function backtrack = [&](int index) {
if(index == digits.size()) {
result.push_back(path);
return;
}
string choices = letters[digits[index]];
for(char ch : choices) {
path.push_back(ch);
backtrack(index+1);
path.pop_back();
}
};
backtrack(0);
return result;
}
};
int main() {
Solution sol;
vector res = sol.letterCombinations("23");
for(string s : res) cout << s << " ";
}
char *letters[] = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
void backtrack(char *digits, int index, char *path, int pathLen) {
if(digits[index] == '\0') {
path[pathLen] = '\0';
printf("%s\n", path);
return;
}
char *choices = letters[digits[index]-'0'];
for(int i=0; choices[i]; i++) {
path[pathLen] = choices[i];
backtrack(digits, index+1, path, pathLen+1);
}
}
int main() {
char digits[] = "23";
char path[100];
if(strlen(digits) > 0) backtrack(digits, 0, path, 0);
return 0;
}
class Solution {
Dictionary letters = new Dictionary() {
{'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
{'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"}
};
public IList LetterCombinations(string digits) {
List result = new List();
if(digits.Length == 0) return result;
void Backtrack(int index, List path) {
if(index == digits.Length) {
result.Add(new string(path.ToArray()));
return;
}
string choices = letters[digits[index]];
foreach(char c in choices) {
path.Add(c);
Backtrack(index+1, path);
path.RemoveAt(path.Count-1);
}
}
Backtrack(0, new List());
return result;
}
static void Main() {
Solution sol = new Solution();
var res = sol.LetterCombinations("23");
foreach(var s in res) Console.Write(s + " ");
}
}
