Backtracking

Foundation drill for this topic

Drill #76 — Letter combinations of phone

Medium Backtrack+Prune

In plain English: Given phone number digits, list all possible letter combinations from the keypad (like T9).

Each digit maps to 3-4 letters. Build combinations by choosing one letter per digit and backtracking — the recursion tree has at most 4^n leaves.

Prompt

Given a string of digits 2-9, return all possible letter combinations that the number could represent (phone keypad mapping).

Try to write it from scratch before scrolling down.

Solution

def letter_combinations(digits):
    if not digits:
        return []
    phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
             '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    result = []
    def backtrack(idx, path):
        if idx == len(digits):
            result.append(''.join(path))
            return
        for c in phone[digits[idx]]:
            path.append(c)
            backtrack(idx + 1, path)
            path.pop()  # backtrack
    backtrack(0, [])
    return result

# Test: letter_combinations("23") == ["ad","ae","af","bd","be","bf","cd","ce","cf"]

O(4^n) time · O(n) space

Related Micro Drills

Quick recall drills to reinforce this pattern.

193 Letter combinations of phone number Backtracking 15s

Each digit maps to letters. At each position, branch on all mapped letters. O(4^n) worst case.

def letterCombinations(digits):
    if not digits: return []
    phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
             '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    res = []
    def backtrack(i, path):
        if i == len(digits):
            res.append(''.join(path))
            return
        for ch in phone[digits[i]]:
            path.append(ch)
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

34 Push and pop Stack Discipline 5s

Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.

stack = []
stack.append(x)
stack.pop()

38 Monotonic stack template Stack Discipline 10s

Monotonic stacks find next-greater/smaller elements in O(n). Key for histogram and temperature problems.

stack = []
for x in a:
    while stack and stack[-1] &gt;= x:
        stack.pop()
    stack.append(x)

See all drills in Backtracking →