Letter Combinations of a Phone Number: LeetCode #17 Walkthrough

Letter combinations phone number leetcode problem #17 is widely considered the best first backtracking problem you can attempt. Unlike Subsets (#78) or Permutations (#46), the choices at each position are completely fixed by the input digit — there is no need for visited tracking, duplicate handling, or index management.

If you have been avoiding backtracking because it feels abstract or intimidating, this problem is your on-ramp. The decision tree is small, the logic is intuitive, and the pattern transfers directly to every harder backtracking problem you will encounter.

By the end of this walkthrough, you will understand the core backtracking template — build a partial solution, recurse, and backtrack — through the simplest possible lens. YeetCode flashcards can help you internalize this pattern so it becomes second nature.

Given a string of digits from 2 to 9, return all possible letter combinations that the number could represent on a phone keypad. This is the same mapping from old T9 cell phones: 2 maps to "abc", 3 maps to "def", and so on up to 9 mapping to "wxyz".

For example, the input "23" produces ["ad","ae","af","bd","be","bf","cd","ce","cf"]. Digit 2 contributes three letters (a, b, c) and digit 3 contributes three letters (d, e, f), giving 3 x 3 = 9 total combinations.

The output order does not matter, and the input will never contain 0 or 1 since those digits have no letter mapping on a phone keypad. An empty input string should return an empty array.

The backtracking approach works by building each combination one character at a time. For each digit in the input, you iterate over its corresponding letters. You add one letter to the current combination, recurse to process the next digit, and then remove that letter (backtrack) to try the next option.

The base case is straightforward: when the current combination has the same length as the input digits string, you have a complete combination and add it to the result. There is no need for a visited set because each digit position is independent — digit 0 always picks from one set of letters, digit 1 from another, and they never overlap.

This is what makes phone keypad backtracking simpler than Subsets or Permutations. In Subsets, you decide include-or-skip for each element. In Permutations, you pick from remaining unused elements. Here, each position has a fixed, non-overlapping set of choices determined entirely by the digit.

The implementation starts with a digit-to-letter mapping. You can use a hash map or simply an array indexed by digit. The mapping is: 2="abc", 3="def", 4="ghi", 5="jkl", 6="mno", 7="pqrs", 8="tuv", 9="wxyz". Notice that 7 and 9 have four letters while the rest have three.

The backtrack function takes the current index into the digits string and the current combination being built. At each level of recursion, it looks up the letters for digits[index], iterates over them, appends each to the current string, and recurses with index + 1.

Time complexity is O(4^n * n) where n is the number of digits. The 4 comes from the maximum letters per digit (7 and 9 have four letters). Each complete combination takes O(n) to copy into the result. Space complexity is O(n) for the recursion stack depth, not counting the output.

Walking through "23" makes the decision tree concrete. The root of the tree is an empty string. At level 0, digit 2 maps to {a, b, c}, so the tree branches into three paths: "a", "b", and "c".

At level 1, digit 3 maps to {d, e, f}. Each of the three branches from level 0 spawns three more branches. "a" becomes "ad", "ae", "af". "b" becomes "bd", "be", "bf". "c" becomes "cd", "ce", "cf". That gives 3 x 3 = 9 leaf nodes, each a complete combination.

The backtracking happens automatically as the recursion unwinds. After exploring "ad", the function backtracks to "a" and tries "ae", then "af". After exhausting all letters for digit 3 under "a", it backtracks to the root and starts down "b".

For a longer input like "234", the tree would have three levels: 3 x 3 x 3 = 27 combinations. For "79", it would be 4 x 4 = 16 combinations since both 7 and 9 have four letters.

The most important edge case is an empty input string. When digits is empty, return an empty array — not an array containing an empty string. This is a common trap that trips up submissions.

A single digit input like "2" should return ["a","b","c"] — three combinations, each a single character. This verifies your base case works correctly with just one level of recursion.

Digits 7 and 9 deserve special attention because they map to four letters instead of three. If your mapping hardcodes three letters per digit, you will miss "s" for 7 and "z" for 9. Always verify your mapping includes: 7="pqrs" and 9="wxyz".

Letter Combinations (#17) teaches the purest form of the backtracking template: enumerate choices at each position, build a partial solution, recurse, and undo. Every harder backtracking problem — Subsets, Permutations, Combination Sum, N-Queens — uses this exact same skeleton.

The key insight is that backtracking with fixed choices per position is the simplest variant. Once you are comfortable generating all phone number letter combinations, you can layer on the additional complexity that other problems introduce: skip-or-include decisions in Subsets, used-element tracking in Permutations, and pruning in Combination Sum.

Practice this problem until you can write the solution from memory in under five minutes. Use YeetCode flashcards to drill the digit-to-letter mapping and the backtracking template. Once this pattern is automatic, the rest of backtracking becomes a matter of small adjustments rather than rethinking from scratch.