Pattern this teaches:Backtracking with Constraints
Letter Combinations of a Phone Number
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 3
- Core for
- 0 roles
The problem
On an old phone keypad each digit from 2 to 9 stands for a few letters (2 is abc, 3 is def, and so on up to 9 for wxyz). Given a string of such digits, return every letter string it could spell, in any order.
Example 1
- Input
- digits = "23"
- Output
- ["ad","ae","af","bd","be","bf","cd","ce","cf"]
- Why
- Digit 2 maps to "abc" and digit 3 maps to "def". The Cartesian product gives all 9 combinations.
Example 2
- Input
- digits = ""
- Output
- []
- Why
- An empty string produces no combinations.
Example 3
- Input
- digits = "2"
- Output
- ["a","b","c"]
- Why
- Digit 2 maps to three letters: a, b, and c.
Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range ['2', '9']
How to think about it
Updated 2026-09-29Each digit index represents an independent slot that must be assigned one character from that digit's letter set. This is a pure Cartesian product: no pruning or constraint checking is necessary because every combination formed by selecting one letter per digit is valid.
Approaches, worst first
Iterative queue expansion
time O(4^n * n) · space O(4^n * n)
Start with a queue containing an empty string. For each digit, pop every string currently in the queue, concatenate each corresponding letter, and push the new strings back. Generates combinations level-by-level without recursion.
Backtracking character bufferWrite this one
time O(4^n * n) · space O(n)
Maintain a character array or string builder. Recurse with digit index i. Loop over the letters mapped to digits[i], assign to buffer[i], and recurse to i + 1. Join buffer into a string when i == digits.length. Operates with minimal memory allocation.
Where people lose marks · 3
- Returning [""] instead of [] when input digits is empty. An empty string has length 0, which if unhandled triggers the base case and incorrectly appends an empty string to the output.
- Incorrect letter mappings for digits 7 and 9, which contain 4 letters ('pqrs' and 'wxyz') instead of 3.
- String concatenation overhead inside deep recursive calls when an array buffer could be reused.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .