Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
A complete visual walkthrough of the backtracking approach — from phone keypad to recursive tree.
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.
Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
1 <= digits.length <= 4digits[i] is a digit in the range ['2', '9'].Each digit on a phone maps to a set of letters. Given a string of digits, we must return every possible letter combination those digits could represent.
Digits 2-9 each map to 3 or 4 letters. Digit 1 maps to nothing.
2 → abc, 3 → def. Every letter from "2" paired with every letter from "3" gives 3 × 3 = 9 combinations.
For two digits, we could write a double-nested loop. For three digits, a triple-nested loop. But the number of digits is variable (0 to 4), so we cannot hardcode the nesting depth.
// For digits = "23" — works fine with 2 loops for (char c1 : "abc".toCharArray()) for (char c2 : "def".toCharArray()) result.add("" + c1 + c2); // For digits = "234" — need 3 loops for (char c1 : "abc".toCharArray()) for (char c2 : "def".toCharArray()) for (char c3 : "ghi".toCharArray()) result.add("" + c1 + c2 + c3); // For digits = "2345" — need 4 loops... // How many loops for n digits? We can't know at compile time!
// For digits = "23" — works fine with 2 loops for _, c1 := range "abc" { for _, c2 := range "def" { result = append(result, string([]byte{byte(c1), byte(c2)})) } } // For digits = "234" — need 3 loops for _, c1 := range "abc" { for _, c2 := range "def" { for _, c3 := range "ghi" { result = append(result, string([]byte{byte(c1), byte(c2), byte(c3)})) } } } // For digits = "2345" — need 4 loops... // How many loops for n digits? We can't know at compile time!
# For digits = "23" — works fine with 2 loops for c1 in "abc": for c2 in "def": result.append(c1 + c2) # For digits = "234" — need 3 loops for c1 in "abc": for c2 in "def": for c3 in "ghi": result.append(c1 + c2 + c3) # For digits = "2345" — need 4 loops... # How many loops for n digits? We can't know at compile time!
// For digits = "23" — works fine with 2 loops for c1 in "abc".chars() { for c2 in "def".chars() { result.push([c1, c2].iter().collect()); } } // For digits = "234" — need 3 loops for c1 in "abc".chars() { for c2 in "def".chars() { for c3 in "ghi".chars() { result.push([c1, c2, c3].iter().collect()); } } } // For digits = "2345" — need 4 loops... // How many loops for n digits? We can't know at compile time!
// For digits = "23" — works fine with 2 loops for (const c1 of "abc") for (const c2 of "def") result.push(c1 + c2); // For digits = "234" — need 3 loops for (const c1 of "abc") for (const c2 of "def") for (const c3 of "ghi") result.push(c1 + c2 + c3); // For digits = "2345" — need 4 loops... // How many loops for n digits? We can't know at compile time!
The problem: We need a variable number of nested loops, one per digit. This is a classic signal that we need recursion. Each recursive call acts as one "level" of nesting, and the recursion depth adapts to the input size automatically.
We build each combination one character at a time. At each digit position, we try every letter that digit maps to, recurse deeper for the next digit, then undo our choice (backtrack) before trying the next letter.
This creates a decision tree where each level corresponds to a digit, and each branch to a letter choice. For digits = "23":
Each path from root to leaf is one complete combination. The tree has 3 × 3 = 9 leaves = 9 combinations.
Backtracking is DFS on this decision tree. We go deep-first: build "a" → "ad" (record it), backtrack to "a" → "ae" (record it), backtrack to "a" → "af" (record it), then backtrack all the way to root and try "b". The StringBuilder.deleteCharAt call is the "undo" step.
Let's trace every recursive call for digits = "23". Watch the path build up and get undone:
The StringBuilder acts as a shared, mutable path. We append before recursing and delete after returning. This is more efficient than creating new String objects at each level, and it is the standard backtracking pattern in Java.
Make sure your solution handles these correctly before submitting:
When digits = "", there are no digits to map and no combinations to form. The correct output is an empty array []. This must be checked first — if the algorithm seeds the result list with [""] before processing digits, an empty input would incorrectly return [""] instead of []. Guard with an upfront if (!digits.length) return []; check.
Input "2" should return ["a", "b", "c"] — exactly the three letters mapped to that key. There is only one level of the recursion tree, so no combining happens. The result size equals the number of letters on that key: three for most digits, four for 7 (pqrs) and 9 (wxyz).
Traditional phone keypads assign no letters to 0 and 1. The problem statement guarantees the input contains only digits 2–9, so you do not need to handle them. However, if your keypad map is an array indexed from '2', accessing index 0 - '2' or 1 - '2' would be out of bounds — keep this in mind if you extend the solution beyond the problem constraints.
Most keys map to three letters, but 7 maps to pqrs and 9 maps to wxyz. This means the combination count is not simply 3^n — it depends on which digits appear. An input of "79" produces 4 × 4 = 16 combinations, while "23" produces 3 × 3 = 9. Ensure your keypad map stores all four letters for these two keys.
The output size grows exponentially: roughly 3^n to 4^n combinations for an input of length n. LeetCode caps the input at length 4, so the worst case is 4^4 = 256 combinations ("7999" or "9999"). In a real system with no length cap, this blows up fast — length 10 could yield over a million combinations. The algorithm's time complexity is inherently O(4^n) and cannot be improved; all combinations must be enumerated.
class Solution { // Index 0 and 1 are empty — digits 0 and 1 have no letters private static final String[] MAPPING = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); // Guard: empty input returns empty list (not [""]) if (digits.isEmpty()) return result; // Start backtracking from digit index 0 backtrack(digits, 0, new StringBuilder(), result); return result; } private void backtrack(String digits, int index, StringBuilder path, List<String> result) { // Base case: built a complete combination if (index == digits.length()) { result.add(path.toString()); // snapshot the path return; } // Get letters for current digit String letters = MAPPING[digits.charAt(index) - '0']; for (char c : letters.toCharArray()) { path.append(c); // 1. Choose backtrack(digits, index + 1, // 2. Explore path, result); path.deleteCharAt( // 3. Un-choose path.length() - 1); } } }
// Index 0 and 1 are empty — digits 0 and 1 have no letters var mapping = [10]string{ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", } func letterCombinations(digits string) []string { result := []string{} // Guard: empty input returns empty list (not [""]) if len(digits) == 0 { return result } var backtrack func(index int, path []byte) backtrack = func(index int, path []byte) { // Base case: built a complete combination if index == len(digits) { result = append(result, string(path)) // snapshot return } // Get letters for current digit letters := mapping[digits[index]-'0'] for i := 0; i < len(letters); i++ { backtrack(index+1, append(path, letters[i])) // Choose + Explore } } backtrack(0, []byte{}) return result }
# Index 0 and 1 are empty — digits 0 and 1 have no letters MAPPING = [ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" ] def letter_combinations(digits: str) -> list[str]: result: list[str] = [] # Guard: empty input returns empty list (not [""]) if not digits: return result def backtrack(index: int, path: list[str]) -> None: # Base case: built a complete combination if index == len(digits): result.append("".join(path)) # snapshot the path return # Get letters for current digit letters = MAPPING[int(digits[index])] for c in letters: path.append(c) # 1. Choose backtrack(index + 1, path) # 2. Explore path.pop() # 3. Un-choose backtrack(0, []) return result
// Index 0 and 1 are empty — digits 0 and 1 have no letters const MAPPING: [&str; 10] = [ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", ]; impl Solution { pub fn letter_combinations(digits: String) -> Vec<String> { let mut result: Vec<String> = Vec::new(); // Guard: empty input returns empty list (not [""]) if digits.is_empty() { return result; } let bytes = digits.as_bytes(); let mut path = Vec::new(); fn backtrack(bytes: &[u8], index: usize, path: &mut Vec<char>, result: &mut Vec<String>) { // Base case: built a complete combination if index == bytes.len() { result.push(path.iter().collect()); // snapshot return; } // Get letters for current digit let letters = MAPPING[(bytes[index] - b'0') as usize]; for c in letters.chars() { path.push(c); // 1. Choose backtrack(bytes, index + 1, path, result); // 2. Explore path.pop(); // 3. Un-choose } } backtrack(bytes, 0, &mut path, &mut result); result } }
// Index 0 and 1 are empty — digits 0 and 1 have no letters const MAPPING: string[] = [ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" ]; function letterCombinations(digits: string): string[] { const result: string[] = []; // Guard: empty input returns empty list (not [""]) if (digits.length === 0) return result; function backtrack(index: number, path: string[]): void { // Base case: built a complete combination if (index === digits.length) { result.push(path.join("")); // snapshot the path return; } // Get letters for current digit const letters = MAPPING[+digits[index]]; for (const c of letters) { path.push(c); // 1. Choose backtrack(index + 1, path); // 2. Explore path.pop(); // 3. Un-choose } } backtrack(0, []); return result; }
Enter digits and watch the backtracking tree build up step by step. Each step shows the algorithm choosing a letter, exploring deeper, or backtracking.
Each digit maps to at most 4 letters (digits 7 and 9). With n digits, the decision tree has up to 4n leaves. At each leaf we copy n characters into the result, giving O(4n · n) time. The output itself stores 4n strings of length n, so space is also O(4n · n). Auxiliary space (recursion stack + path buffer) is only O(n).
An iterative approach builds combinations by creating new strings at each digit level. For n digits with up to 4 letters each, this produces up to 4n combinations of length n, costing O(4n · n) for both string concatenation work and output storage.
Backtracking explores a decision tree of depth n where each node has up to 4 children. The tree has 4n leaves, and at each leaf we copy n characters into the result. Auxiliary space is only O(n) for the recursion stack and path buffer, but the output itself dominates at O(4n · n).
The output size IS the complexity. When the problem requires generating all possible combinations, there is no way to beat O(4n) — every combination must be produced. Backtracking is already optimal; the only difference between approaches is constant-factor overhead, not asymptotic class. In practice, n ≤ 4, so the maximum output is 44 = 256 strings.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.