Approach Summary
Backtracking: for each digit, try each mapped letter and recurse on the remaining digits. Collect results at leaf nodes.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
Each digit maps to a fixed set of letters, and a complete combination is formed by choosing exactly one letter per digit, in order. The number of combinations is the product of the map sizes — 3 or 4 choices per position — so enumerate them with backtracking. A recursive function receives the current digit index and the path of chosen letters so far. When the index reaches the length of the digits string, the path is a complete combination, so record it. Otherwise, for every letter in the mapping of the current digit, append it, recurse on the next index, and pop it back off. The pop restores the path so every branch shares one buffer instead of copying strings at every step. The search tree has depth equal to the number of digits and branching factor 3 or 4, so the total output size is bounded by 4^len. The empty-digits case must return an empty list, not a list containing an empty string — a common off-by-one. This problem is the simplest member of the digits-mapping family that also includes generate-parentheses and IP-address restoration.
The output contains at most 4^len strings, each of length len, so time and space are O(len · 4^len) in the worst case — this is output-bound and unavoidable.
Solution Code
Solution
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
backtrack(digits, map, 0, new StringBuilder(), res);
return res;
}
private void backtrack(String digits, String[] map, int i, StringBuilder path, List<String> res) {
if (i == digits.length()) {
res.add(path.toString());
return;
}
for (char ch : map[digits.charAt(i) - '0'].toCharArray()) {
path.append(ch);
backtrack(digits, map, i + 1, path, res);
path.deleteCharAt(path.length() - 1);
}
}vector<string> letterCombinations(const string& digits) {
if (digits.empty()) return {};
vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string path;
backtrack(digits, map, 0, path, res);
return res;
}
void backtrack(const string& digits, const vector<string>& map, int i, string& path, vector<string>& res) {
if (i == (int)digits.size()) {
res.push_back(path);
return;
}
for (char ch : map[digits[i] - '0']) {
path.push_back(ch);
backtrack(digits, map, i + 1, path, res);
path.pop_back();
}
}def letter_combinations(digits: str) -> list[str]:
if not digits:
return []
mapping = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
}
res = []
def backtrack(i: int, path: list[str]) -> None:
if i == len(digits):
res.append(''.join(path))
return
for ch in mapping[digits[i]]:
path.append(ch)
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resfunction letterCombinations(digits) {
if (!digits) return [];
const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' };
const res = [];
function backtrack(i, path) {
if (i === digits.length) {
res.push(path.join(''));
return;
}
for (const ch of map[digits[i]]) {
path.push(ch);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return res;
}Edge Cases to Watch
- Empty input — return [] (not [""])
- Digits containing 7 or 9 — their 4-letter maps make the output up to 4x larger
- Digits with a single 1 or 0 — no letters; the standard mapping treats them as empty
- Single digit — returns the letters of that digit as single characters
Master the Backtracking Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.
How to Recognize This Pattern
- "All combinations of letters from phone number"
- Classic backtracking: build combination letter by letter
Complexity Analysis
Time Complexity
O(4ⁿ × n)
Space Complexity
O(n)