Phone Keypad Combinations: why backtracking fits this problem like a glove

The input is a string of up to four digits, each between '2' and '9'. Every digit maps to a group of letters — the old T9 keypad layout. The task is to return every string you can form by picking exactly one letter per digit. For "23" that is nine strings: "ad" through "cf". For "" it is an empty list. Simple to state, and yet the gap between the iterative and recursive implementations tells you something useful about how backtracking thinks.

The problem

Given a string of digits from '2' to '9', return all possible letter combinations that the digit string could represent on a phone keypad, in any order. An empty input produces an empty list. Full statement: LeetCode 17.

Constraints:
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9'].

What the constraints actually force

0 <= digits.length <= 4. That single line does a lot of work. The maximum output size is 4^4 = 256 strings of length 4 — 1024 characters total. This is not O(n^2) vs O(n log n) territory where you need to optimize carefully; the output itself is bounded by a small constant. You must enumerate everything, and no matter how you do it, the work is proportional to the output.

Digits run from '2' to '9'. There is no '0' or '1' in the input — both are unassigned on a phone keypad — so the mapping is complete and contains no gaps to handle. Seven digits map to three letters each; '7' and '9' map to four. The worst-case 4^n bound comes from those two digits.

What these constraints do not tell you to do: prune, memoize, or avoid allocating all results. The output must contain every combination anyway. The only real decision is how you build them — all at once level by level, or one complete string at a time via recursion.

Approach 1: iterative expansion (BFS-style layer build)

Start with a list containing one empty string. For each digit in the input, take every current partial string and extend it with each letter that digit maps to. After processing all digits, the list holds the complete answer.

from typing import List
 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
 
        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
 
        result = ['']
 
        for digit in digits:
            letters = phone_map[digit]
            new_result = []
            for combination in result:
                for letter in letters:
                    new_result.append(combination + letter)
            result = new_result
 
        return result

using System.Collections.Generic;
 
public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits))
            return new List<string>();
 
        var phoneMap = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
 
        var result = new List<string> { "" };
 
        foreach (char digit in digits) {
            string letters = phoneMap[digit];
            var newResult = new List<string>();
            foreach (string combination in result) {
                foreach (char letter in letters) {
                    newResult.Add(combination + letter);
                }
            }
            result = newResult;
        }
 
        return result;
    }
}

For "23", the process unfolds like this. After digit '2': result = ["a", "b", "c"]. After digit '3': each of those three strings gets extended by d, e, f, producing nine strings. Done.

The key observation is that result at every stage represents the full Cartesian product of the digits seen so far. You are building the product incrementally, one factor at a time. This works and is easy to reason about. The downside is that you always hold the full intermediate list in memory during the extend step — the old list and the new list both exist simultaneously.

Complexity: Time O(4^n * n) — at most 4^n combinations, each of length up to n. Space O(4^n * n) — you hold the full intermediate list, and at the step from the last digit, the old list of size 4^(n-1) and the new list of size 4^n coexist.

Approach 2: backtracking — one string at a time

Instead of maintaining a growing list of partial strings, recursion descends the decision tree depth-first: choose a letter for the current digit position, recurse into the next position, add to results only when the string is complete.

from typing import List
 
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
 
        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
 
        result = []
 
        def backtrack(index: int, current: str) -> None:
            if index == len(digits):
                result.append(current)
                return
            for letter in phone_map[digits[index]]:
                backtrack(index + 1, current + letter)
 
        backtrack(0, "")
        return result

using System.Collections.Generic;
using System.Text;
 
public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits))
            return new List<string>();
 
        var phoneMap = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
 
        var result = new List<string>();
 
        void Backtrack(int index, StringBuilder current) {
            if (index == digits.Length) {
                result.Add(current.ToString());
                return;
            }
            foreach (char letter in phoneMap[digits[index]]) {
                current.Append(letter);
                Backtrack(index + 1, current);
                current.Remove(current.Length - 1, 1);
            }
        }
 
        Backtrack(0, new StringBuilder());
        return result;
    }
}

Notice the difference in C# vs Python. Python strings are immutable: current + letter creates a new string object without modifying current, so no explicit undo step is needed. C# uses StringBuilder (mutable) for efficiency, which means you must explicitly remove the last character after each recursive call — the classical backtrack step: add, recurse, remove.

Complexity: Time O(4^n * n) — same bound as iterative, for the same reason. Space O(n) for the call stack (depth equals digits.length, at most 4 levels) plus O(4^n * n) for the output list. The call stack is tiny compared to the iterative approach's intermediate allocations.

Hand trace through "23"

backtrack(index=0, current="")
  digit='2', letters="abc"
  -> letter='a': backtrack(index=1, current="a")
       digit='3', letters="def"
       -> letter='d': backtrack(index=2, current="ad")  [base: append "ad"]
       -> letter='e': backtrack(index=2, current="ae")  [base: append "ae"]
       -> letter='f': backtrack(index=2, current="af")  [base: append "af"]
  -> letter='b': backtrack(index=1, current="b")
       -> letter='d': append "bd"
       -> letter='e': append "be"
       -> letter='f': append "bf"
  -> letter='c': backtrack(index=1, current="c")
       -> letter='d': append "cd"
       -> letter='e': append "ce"
       -> letter='f': append "cf"

result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

The base case fires exactly at index == len(digits). There is no partial-result maintenance, no growing list to update mid-traversal. Each leaf of the recursion tree holds one complete answer.

Edge cases worth reasoning about

Empty input (digits = ""). Both approaches check for this at the top and return []. If you skip this check, the iterative approach returns [''] (the seed) — which the problem says is wrong — and the backtracking approach correctly returns [] because backtrack(0, "") immediately hits index == 0 == len("") and appends the empty string. So the empty-string guard is strictly necessary for the iterative version, slightly redundant but clarifying for the backtracking version.

Single digit (digits = "2"). Iterative: the seed [''] gets extended to ['a','b','c'], correct. Backtracking: three leaf calls, each one character deep. Both produce ["a","b","c"].

Digits '7' or '9' (four letters each). The only place where 4^n becomes a tighter bound than 3^n. digits = "7777" yields 4^4 = 256 results of length 4. The mapping {'7': 'pqrs', '9': 'wxyz'} handles this — just confirm you did not accidentally type three-letter strings for those two.

All same digit (digits = "9999"). Produces 256 four-character strings from {w,x,y,z}^4. Both approaches handle this identically; there is nothing structurally different about repeated digits.

Maximum length (digits.length = 4). With digits all being '7' or '9', you get 256 output strings. With digits all being three-letter keys, you get 3^4 = 81. In either case it is a small constant — the constraint digits.length <= 4 was clearly chosen to guarantee this.

Comparison table

The time bound is identical. The space story is different: iterative holds two full lists simultaneously during each extension step (old and new). Backtracking holds one n-deep call stack and accumulates results only at leaves.

For n <= 4 and at most 256 results, neither approach will cause any resource issue. This is a correctness and clarity choice, not a performance choice.

What I would ship and why

I reach for the backtracking version every time. Not because of the stack vs heap allocation difference — with n = 4 that is not real. It is because the backtracking code is a direct translation of how you think about the problem: pick a letter, go deeper, come back, try the next letter. The iterative version requires you to hold in your head that result is "all combinations of the prefix so far" — a correct but less natural invariant.

The other reason: backtracking scales to constrained variants of this problem in a way that iteration does not. If you add a condition ("only combinations that don't repeat the same letter consecutively") or a pruning rule, you drop it into the backtrack function and it works immediately. With the iterative approach you have to restructure the outer loop logic.

Where this sits in the backtracking series

This is problem 8 in the series, after Subsets, Permutations, Combination Sum, and their variants. Those problems involved choosing elements from a single collection. Letter Combinations is structurally different: you have one group of choices per position (digits[i] -> letters), and the groups are all different sizes and contents. That is the new idea here — the decision tree is not symmetric. Each level branches differently depending on which digit you are at.

The underlying pattern is still the same: at each node in the search tree, enumerate all choices, recurse, undo. What changes is how the choices are defined.

Generate Parentheses (22) is the natural companion: choices at each step are constrained by validity rules (you can only close if open count allows), not by an external map. Backtracking with pruning, not backtracking with lookup.

Combination Sum (39) lets you pick from the same collection repeatedly. The branching factor is uniform across levels. Letter Combinations has non-uniform branching — three letters for some digits, four for others — but no repeated picks.

Permutations (46) has a fixed alphabet and all choices at every level, but you cannot reuse an element at the same position. Different constraint, same DFS skeleton.

Word Search (79) extends the idea spatially: instead of choosing from a map, you choose from neighbors on a grid. The backtracking skeleton is unchanged; only what counts as "a valid next choice" is different.