Letter Combinations of a Phone Number (LeetCode 17)
Given a string of digits from 2 to 9, return every letter combination the digit string could spell out under a telephone-keypad mapping, in any order.
Each digit key 2-9 maps to a fixed group of 3 or 4 letters, exactly like on an old telephone keypad; the digit 1 has no letters mapped to it.
Worked Examples
digits = "23"["ad","ae","af","bd","be","bf","cd","ce","cf"]2 maps to abc and 3 to def, so there are 3 * 3 = 9 letter pairs.digits = "2"["a","b","c"]2 alone gives a, b and c.⚖️Formal Constraints & Bounds
1 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Core Insight
Each digit is a slot with its own letters and no choice limits another, so the recursion depth is the slot: try every letter of slot index, then fill slot index + 1. Every branch reaches a full combination, and only a full-length path is saved.
Real-World Scenario & Production Applications
T9 predictive text input engines, vanity phone number lookup generators.
Subproblems & Recurrence Decomposition3 Phases
Slot index is the digit digits[index]; its only options are the letters on that key, keypad[digits[index]].
for letter in keypad[digits[index]]:Step-by-Step Execution Trace Table
[ "" ] (Root, Depth 0) / | \ choose 'a'/ choose 'b'| choose 'c'\ / | \ [ "a" ] [ "b" ] [ "c" ] (Depth 1) / | \ / | \ / | \ d e f d e f d e f / | \ / | \ / | \ "ad" "ae" "af""bd" "be" "bf""cd" "ce" "cf" (Depth 2, Base Case: len == 2) ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ Step-by-Step Decision Trace
- Step 1 (Root, d=0):
path = []. Digit'2'provides choices['a', 'b', 'c']. - Step 2 (Choose 'a', d=1): Append
'a'path = ['a']. Digit'3'provides choices['d', 'e', 'f']. - Step 3 (Choose 'd', d=2): Append
'd'path = ['a', 'd']. Base Case (len == 2): Record"ad"✅. - Step 4 (Backtrack / Pop 'd', d=1):
path = ['a']. Advance choices to'e'. - Step 5 (Choose 'e', d=2): Append
'e'path = ['a', 'e']. Base Case: Record"ae"✅. - Step 6 (Backtrack / Pop 'e', d=1):
path = ['a']. Advance choices to'f'. - Step 7 (Choose 'f', d=2): Append
'f'path = ['a', 'f']. Base Case: Record"af"✅. - Step 8 (Backtrack / Pop 'f' & Pop 'a', d=0):
path = []. Subtree'a'complete; next root candidate is'b'. - Step 9 (Choose 'b', d=1): Append
'b'path = ['b']. Digit'3'provides choices['d', 'e', 'f']. - Step 10 (Choose 'd', d=2): Append
'd'path = ['b', 'd']. Base Case: Record"bd"✅. - Step 11 (Backtrack / Pop 'd', d=1):
path = ['b']. Advance choices to'e'. - Step 12 (Choose 'e', d=2): Append
'e'path = ['b', 'e']. Base Case: Record"be"✅. - Step 13 (Backtrack / Pop 'e', d=1):
path = ['b']. Advance choices to'f'. - Step 14 (Choose 'f', d=2): Append
'f'path = ['b', 'f']. Base Case: Record"bf"✅. - Step 15 (Backtrack / Pop 'f' & Pop 'b', d=0):
path = []. Subtree'b'complete; next root candidate is'c'. - Step 16 (Choose 'c', d=1): Append
'c'path = ['c']. Digit'3'provides choices['d', 'e', 'f']. - Step 17 (Choose 'd', d=2): Append
'd'path = ['c', 'd']. Base Case: Record"cd"✅. - Step 18 (Backtrack / Pop 'd', d=1):
path = ['c']. Advance choices to'e'. - Step 19 (Choose 'e', d=2): Append
'e'path = ['c', 'e']. Base Case: Record"ce"✅. - Step 20 (Backtrack / Pop 'e', d=1):
path = ['c']. Advance choices to'f'. - Step 21 (Choose 'f', d=2): Append
'f'path = ['c', 'f']. Base Case: Record"cf"✅. - Step 22 (Backtrack / Pop 'f' & Pop 'c', d=0):
path = []. All 9 Cartesian combinations generated. Search Complete: Output:['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'].
digits = "23"Expected:["ad","ae","af","bd","be","bf","cd","ce","cf"]| 1 | keypad = {...} |
| 2 | results = [] |
| 3 | path = [] |
| 4 | def backtrack(index): |
| 5 | if index == len(digits): |
| 6 | results.append(''.join(path)) |
| 7 | return |
| 8 | for letter in keypad[digits[index]]: |
| 9 | path.append(letter) |
| 10 | backtrack(index + 1) |
| 11 | path.pop() |
| 12 | backtrack(0) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This archetype is the master template every other backtracking problem in this pattern is a variation of, and the simplest one: each position of the answer is its own slot with its own list of options, and any mix of choices is allowed. So the recursion depth is the slot: backtrack(index) fills slot index with each of its options in turn and moves on to index + 1. No start index, no used set, nothing to prune.
🌳 The Analogy: A Decision Tree You Walk and Un-Walk
Every backtracking problem has the same shape: you're standing at a fork in a decision tree, you pick one path, walk down it, and when you hit a dead end (or a finished answer), you walk back up to the fork and try the next path, leaving no trace of having gone down the first one. The call stack itself is the memory of "how did I get here": each stack frame is one decision on the path from the root.
🔑 The Key Idea in the Code
path.pop() is what makes this backtracking rather than plain recursion: without it, every branch would see the leftover choices from every branch explored before it. And the save sits only behind index == len(digits): a shorter path still has empty slots, so saving at every node (the Subsets habit) would add partial strings such as "a".
Saving a partial path: save only when
index == len(digits). A shorterpathstill has empty slots, so saving at every node, the Subsets habit, adds partial strings such as"a"beside"ad".A shared-pool loop: loop over
keypad[digits[index]]and recurse withbacktrack(index + 1): the depth is the slot. Afor i in range(start, ...)loop from Combinations picks from one shared pool and skips slots.Forgetting to undo:
path.pop()afterbacktrack(index + 1)frees the slot. Without it the next letter is appended after the old one andpathgrows pastlen(digits).Wrong options for a slot: give each slot only its real options. Keys 7 and 9 have four letters, not three; and in Letter Case Permutation (LC 784) a digit has one option, so
[ch.lower(), ch.upper()]on a digit makes every string twice.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for every letter combination, and each digit brings its own 3 or 4 letters: one position per digit, each with its own short option list, and any mix is allowed. That is a Cartesian product: one choice per slot, built by backtracking over the slots.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path holds exactly one letter for each of the digits digits[0..index-1], in order, so len(path) == index in every call. backtrack(index) loops over keypad[digits[index]] only, and saves "".join(path) exactly when index == len(digits).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Hard-coding three letters per key: keys
7and9have four (pqrs,wxyz), so"79"gives 16 combinations, not 9.A single digit: the answer is that key's letters, one string each, and the same base case
index == len(digits)handles it with no special code.Building a new string at every level (
path + letter) instead of one sharedpathjoined once per full combination: it copies the prefix at every node for nothing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use One Choice per Slot. Every digit is a slot, and its key's three or four letters are that slot's only options; no choice limits another. So my recursion depth is the slot: backtrack of index loops over the letters of digits at index, appends one to path, calls backtrack of index plus one, and pops it. There is no start index and no used set, and nothing needs pruning, because every branch reaches a full combination and each one is built exactly once, one letter per slot in order. The trap is where I save: only when index equals the number of digits, because a shorter path still has empty slots, and saving at every node like in Subsets would add partial strings. With N digits there are at most 4 to the N combinations and each costs
O(N)to join, so O(N times 4 to the N) time, andO(N)space for the recursion and path, output not counted."
Complexity & Mathematical Proof
O(N * 4^N)
Look at the code: backtrack(index) loops over keypad[digits[index]], 3 or 4 letters, and calls backtrack(index + 1) once per letter, so level index of the call tree has at most 4^index calls and the last level, index == len(digits), has at most 4^N. Each leaf runs "".join(path) on N letters: O(N). The inner calls do O(1) work per letter (append, call, pop), and there are fewer inner calls than leaves times 4/3, so the leaves dominate: O(N * 4^N).
O(N) recursion stack and path, output not counted
Look at what is alive at once: the call stack holds one backtrack frame per filled slot, at most N + 1, and path holds at most N letters. keypad has 8 fixed entries. results is the answer itself (up to 4^N strings of length N), the output, not counted.
T(N) = (at most 4^N leaves) x O(N) join + (inner calls) x O(1) = O(N * 4^N)
Derivation Progression
for letter in keypad[digits[index]]: 3 or 4 children per call
Keys 7 and 9 have 4 letters, the others 3, so each call has at most 4 children.
backtrack(index + 1): N levels, then index == len(digits)
One level per slot, so the tree has at most 4^N leaves, one per combination.
"".join(path): O(N)
Each full combination is joined once from N letters.
4^N x O(N) + O(4^N) inner calls = O(N * 4^N)
Inner calls do constant work per letter and are fewer than the leaves times 4/3, so the leaves dominate.
Variable Definitions
len(digits), the number of slots (1 to 4)
Memory Architecture & Bounds
O(N): one backtrack frame per filled slot
O(N): path, one letter per filled slot; keypad is fixed size
O(N * 4^N): results, the answer itself, not counted
Boundary Best / Worst Cases
: every digit is a three-letter key
: every digit is 7 or 9
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every letter combination", "each digit maps to 3 or 4 letters". One position per digit, each with its own option list, any mix allowed: One Choice per Slot, a backtracking walk with one recursion level per slot.
digits, so at most combinations of length 4. The output itself is the cost: it grows as , so for larger inputs production code streams combinations (a generator) instead of building the whole list.
Keep one shared path and undo with pop() rather than copying strings at every level. When the output is streamed, the slot order fixes the output order (lexicographic by slot when each slot's options are sorted), which callers may rely on.
Letter Combinations of a Phone Number (LeetCode 17)
Given a string of digits from 2 to 9, return every letter combination the digit string could spell out under a telephone-keypad mapping, in any order.
Each digit key 2-9 maps to a fixed group of 3 or 4 letters, exactly like on an old telephone keypad; the digit 1 has no letters mapped to it.
Worked Examples
digits = "23"["ad","ae","af","bd","be","bf","cd","ce","cf"]2 maps to abc and 3 to def, so there are 3 * 3 = 9 letter pairs.digits = "2"["a","b","c"]2 alone gives a, b and c.⚖️Formal Constraints & Bounds
1 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Core Insight
Each digit is a slot with its own letters and no choice limits another, so the recursion depth is the slot: try every letter of slot index, then fill slot index + 1. Every branch reaches a full combination, and only a full-length path is saved.
Real-World Scenario & Production Applications
T9 predictive text input engines, vanity phone number lookup generators.
Subproblems & Recurrence Decomposition3 Phases
Slot index is the digit digits[index]; its only options are the letters on that key, keypad[digits[index]].
for letter in keypad[digits[index]]:Step-by-Step Execution Trace Table
[ "" ] (Root, Depth 0) / | \ choose 'a'/ choose 'b'| choose 'c'\ / | \ [ "a" ] [ "b" ] [ "c" ] (Depth 1) / | \ / | \ / | \ d e f d e f d e f / | \ / | \ / | \ "ad" "ae" "af""bd" "be" "bf""cd" "ce" "cf" (Depth 2, Base Case: len == 2) ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ Step-by-Step Decision Trace
- Step 1 (Root, d=0):
path = []. Digit'2'provides choices['a', 'b', 'c']. - Step 2 (Choose 'a', d=1): Append
'a'path = ['a']. Digit'3'provides choices['d', 'e', 'f']. - Step 3 (Choose 'd', d=2): Append
'd'path = ['a', 'd']. Base Case (len == 2): Record"ad"✅. - Step 4 (Backtrack / Pop 'd', d=1):
path = ['a']. Advance choices to'e'. - Step 5 (Choose 'e', d=2): Append
'e'path = ['a', 'e']. Base Case: Record"ae"✅. - Step 6 (Backtrack / Pop 'e', d=1):
path = ['a']. Advance choices to'f'. - Step 7 (Choose 'f', d=2): Append
'f'path = ['a', 'f']. Base Case: Record"af"✅. - Step 8 (Backtrack / Pop 'f' & Pop 'a', d=0):
path = []. Subtree'a'complete; next root candidate is'b'. - Step 9 (Choose 'b', d=1): Append
'b'path = ['b']. Digit'3'provides choices['d', 'e', 'f']. - Step 10 (Choose 'd', d=2): Append
'd'path = ['b', 'd']. Base Case: Record"bd"✅. - Step 11 (Backtrack / Pop 'd', d=1):
path = ['b']. Advance choices to'e'. - Step 12 (Choose 'e', d=2): Append
'e'path = ['b', 'e']. Base Case: Record"be"✅. - Step 13 (Backtrack / Pop 'e', d=1):
path = ['b']. Advance choices to'f'. - Step 14 (Choose 'f', d=2): Append
'f'path = ['b', 'f']. Base Case: Record"bf"✅. - Step 15 (Backtrack / Pop 'f' & Pop 'b', d=0):
path = []. Subtree'b'complete; next root candidate is'c'. - Step 16 (Choose 'c', d=1): Append
'c'path = ['c']. Digit'3'provides choices['d', 'e', 'f']. - Step 17 (Choose 'd', d=2): Append
'd'path = ['c', 'd']. Base Case: Record"cd"✅. - Step 18 (Backtrack / Pop 'd', d=1):
path = ['c']. Advance choices to'e'. - Step 19 (Choose 'e', d=2): Append
'e'path = ['c', 'e']. Base Case: Record"ce"✅. - Step 20 (Backtrack / Pop 'e', d=1):
path = ['c']. Advance choices to'f'. - Step 21 (Choose 'f', d=2): Append
'f'path = ['c', 'f']. Base Case: Record"cf"✅. - Step 22 (Backtrack / Pop 'f' & Pop 'c', d=0):
path = []. All 9 Cartesian combinations generated. Search Complete: Output:['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'].
digits = "23"Expected:["ad","ae","af","bd","be","bf","cd","ce","cf"]| 1 | keypad = {...} |
| 2 | results = [] |
| 3 | path = [] |
| 4 | def backtrack(index): |
| 5 | if index == len(digits): |
| 6 | results.append(''.join(path)) |
| 7 | return |
| 8 | for letter in keypad[digits[index]]: |
| 9 | path.append(letter) |
| 10 | backtrack(index + 1) |
| 11 | path.pop() |
| 12 | backtrack(0) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This archetype is the master template every other backtracking problem in this pattern is a variation of, and the simplest one: each position of the answer is its own slot with its own list of options, and any mix of choices is allowed. So the recursion depth is the slot: backtrack(index) fills slot index with each of its options in turn and moves on to index + 1. No start index, no used set, nothing to prune.
🌳 The Analogy: A Decision Tree You Walk and Un-Walk
Every backtracking problem has the same shape: you're standing at a fork in a decision tree, you pick one path, walk down it, and when you hit a dead end (or a finished answer), you walk back up to the fork and try the next path, leaving no trace of having gone down the first one. The call stack itself is the memory of "how did I get here": each stack frame is one decision on the path from the root.
🔑 The Key Idea in the Code
path.pop() is what makes this backtracking rather than plain recursion: without it, every branch would see the leftover choices from every branch explored before it. And the save sits only behind index == len(digits): a shorter path still has empty slots, so saving at every node (the Subsets habit) would add partial strings such as "a".
Saving a partial path: save only when
index == len(digits). A shorterpathstill has empty slots, so saving at every node, the Subsets habit, adds partial strings such as"a"beside"ad".A shared-pool loop: loop over
keypad[digits[index]]and recurse withbacktrack(index + 1): the depth is the slot. Afor i in range(start, ...)loop from Combinations picks from one shared pool and skips slots.Forgetting to undo:
path.pop()afterbacktrack(index + 1)frees the slot. Without it the next letter is appended after the old one andpathgrows pastlen(digits).Wrong options for a slot: give each slot only its real options. Keys 7 and 9 have four letters, not three; and in Letter Case Permutation (LC 784) a digit has one option, so
[ch.lower(), ch.upper()]on a digit makes every string twice.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for every letter combination, and each digit brings its own 3 or 4 letters: one position per digit, each with its own short option list, and any mix is allowed. That is a Cartesian product: one choice per slot, built by backtracking over the slots.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path holds exactly one letter for each of the digits digits[0..index-1], in order, so len(path) == index in every call. backtrack(index) loops over keypad[digits[index]] only, and saves "".join(path) exactly when index == len(digits).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Hard-coding three letters per key: keys
7and9have four (pqrs,wxyz), so"79"gives 16 combinations, not 9.A single digit: the answer is that key's letters, one string each, and the same base case
index == len(digits)handles it with no special code.Building a new string at every level (
path + letter) instead of one sharedpathjoined once per full combination: it copies the prefix at every node for nothing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use One Choice per Slot. Every digit is a slot, and its key's three or four letters are that slot's only options; no choice limits another. So my recursion depth is the slot: backtrack of index loops over the letters of digits at index, appends one to path, calls backtrack of index plus one, and pops it. There is no start index and no used set, and nothing needs pruning, because every branch reaches a full combination and each one is built exactly once, one letter per slot in order. The trap is where I save: only when index equals the number of digits, because a shorter path still has empty slots, and saving at every node like in Subsets would add partial strings. With N digits there are at most 4 to the N combinations and each costs
O(N)to join, so O(N times 4 to the N) time, andO(N)space for the recursion and path, output not counted."
Complexity & Mathematical Proof
O(N * 4^N)
Look at the code: backtrack(index) loops over keypad[digits[index]], 3 or 4 letters, and calls backtrack(index + 1) once per letter, so level index of the call tree has at most 4^index calls and the last level, index == len(digits), has at most 4^N. Each leaf runs "".join(path) on N letters: O(N). The inner calls do O(1) work per letter (append, call, pop), and there are fewer inner calls than leaves times 4/3, so the leaves dominate: O(N * 4^N).
O(N) recursion stack and path, output not counted
Look at what is alive at once: the call stack holds one backtrack frame per filled slot, at most N + 1, and path holds at most N letters. keypad has 8 fixed entries. results is the answer itself (up to 4^N strings of length N), the output, not counted.
T(N) = (at most 4^N leaves) x O(N) join + (inner calls) x O(1) = O(N * 4^N)
Derivation Progression
for letter in keypad[digits[index]]: 3 or 4 children per call
Keys 7 and 9 have 4 letters, the others 3, so each call has at most 4 children.
backtrack(index + 1): N levels, then index == len(digits)
One level per slot, so the tree has at most 4^N leaves, one per combination.
"".join(path): O(N)
Each full combination is joined once from N letters.
4^N x O(N) + O(4^N) inner calls = O(N * 4^N)
Inner calls do constant work per letter and are fewer than the leaves times 4/3, so the leaves dominate.
Variable Definitions
len(digits), the number of slots (1 to 4)
Memory Architecture & Bounds
O(N): one backtrack frame per filled slot
O(N): path, one letter per filled slot; keypad is fixed size
O(N * 4^N): results, the answer itself, not counted
Boundary Best / Worst Cases
: every digit is a three-letter key
: every digit is 7 or 9
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every letter combination", "each digit maps to 3 or 4 letters". One position per digit, each with its own option list, any mix allowed: One Choice per Slot, a backtracking walk with one recursion level per slot.
digits, so at most combinations of length 4. The output itself is the cost: it grows as , so for larger inputs production code streams combinations (a generator) instead of building the whole list.
Keep one shared path and undo with pop() rather than copying strings at every level. When the output is streamed, the slot order fixes the output order (lexicographic by slot when each slot's options are sorted), which callers may rely on.