17. Letter Combinations of a Phone Number

Reformulated question¶

Given a string of digits 2 to 9, return every string formed by choosing one phone-keypad letter for each digit.

Example:

digits = "23"
2 -> abc
3 -> def
result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Key trick¶

Build the answer one position at a time.

• Each digit gives a small set of choices.
• Use backtracking/DFS:
  • pick one letter for the current digit,
  • recurse to the next digit,
  • when the built string has length len(digits), save it.

This is the recursive version of nested loops where the number of loops is unknown in advance.

Trap¶

• Forgetting the empty-input case.
  • LeetCode expects [] for "", not [""].
• Appending too early.
  • Only append when all digits were processed.
• Mutating shared state incorrectly in iterative/backtracking code.
  • If you use one string/list path, you must undo the last choice when returning.
• Hardcoding nested loops.
  • Works only for fixed length, but input length is variable.

Why this question is interesting¶

It is a tiny, clean backtracking problem.

• It shows how recursion replaces an arbitrary number of nested loops.
• It is easy to explain, easy to test, and exposes base-case/state-management mistakes quickly.

Solve the problem with idiomatic Python¶

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        # LeetCode usually expects [] for empty input.
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []
        path = []

        def dfs(i: int) -> None:
            # If we chose one letter for every digit, we built one answer.
            if i == len(digits):
                result.append("".join(path))
                return

            # Try every possible letter for the current digit.
            for ch in phone[digits[i]]:
                path.append(ch)   # choose
                dfs(i + 1)        # explore
                path.pop()        # un-choose

        dfs(0)
        return result

Complexity:

• Time: \(O(n \cdot 4^n)\)
• Space: \(O(n)\) auxiliary, ignoring output

Also valid direct-library style solution¶

from itertools import product


class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        return ["".join(chars) for chars in product(*(phone[d] for d in digits))]

Pytest test¶

import pytest


@pytest.mark.parametrize(
    ("digits", "expected"),
    [
        ("", []),
        ("2", ["a", "b", "c"]),
        ("23", ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]),
        ("7", ["p", "q", "r", "s"]),
        ("79", [
            "pw", "px", "py", "pz",
            "qw", "qx", "qy", "qz",
            "rw", "rx", "ry", "rz",
            "sw", "sx", "sy", "sz",
        ]),
    ],
)
def test_letterCombinations(digits, expected):
    assert Solution().letterCombinations(digits) == expected

Comment your solution¶

Your recursive solution is correct and already interview-good.

• Good:
  • Clear mapping.
  • Correct DFS structure.
  • Easy base case.
• Small improvements:
  • Return [] for empty input.
  • Use strings in the map instead of lists; simpler.
  • Avoid nonlocal combinations; appending to a captured list does not need it.
  • Using a path list plus append/pop is slightly more idiomatic for backtracking than s + ch.

## Solution
# WORKS
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        d_to_chars = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"],
        }
        combinations = []

        # `i` index in digits
        # `s` the string we're building
        def dfs(i, s):
            nonlocal combinations
            if i >= len(digits):
                combinations.append(s)
                return
            digit = digits[i]
            chars = d_to_chars[digit]
            for ch in chars:
                dfs(i + 1, s + ch)

        dfs(0, "")
        return combinations


# Easier problem/question to help me answer the original one
# how to convert following into backtracking?
#
# for i in ["a", "b", "c"]:
#     for j in ["d", "e", "f"]:
#         for k in ["g", "h", "i"]:
#             combinations.append(i + j + k)
# adg
# adh
# adi
# --- backtracking
# aeg
# aeh
# aei
# --- backtracking
# afg
# afh
# afi
# --- backtracking
# --- backtracking
# bdg
# bdh
# bdi
# --- backtracking
# beg
# ...


# DON'T WORK - iterative
class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        d_to_chars = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"],
        }
        combinations = []

        i = 0
        chars = d_to_chars[digits[0]].copy()
        stack = [(0, chars)]  # digit, chars
        s = ""
        while stack:
            print(f"stack: {stack}")
            if i >= len(digits):
                combinations.append(s)
                i = stack[len(stack) - 1][0]
                s = s[:i]
                continue
            j, chars = stack.pop()
            ch = chars.pop()  # reverse order (different from recursive dfs I wrote)
            s = s + ch
            if chars:
                stack.append((j, chars))
            i += 1
            if i < len(digits):
                stack.append((i, d_to_chars[digits[i]].copy()))

        return combinations


# DON'T WORK - we're missing one pair 'ad'
Solution().letterCombinations("23")  # ['cf', 'ce', 'cd', 'bf', 'be', 'bd', 'af', 'ae']

A cleaned-up version close to yours:

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []

        def dfs(i: int, s: str) -> None:
            if i == len(digits):
                result.append(s)
                return

            for ch in phone[digits[i]]:
                dfs(i + 1, s + ch)

        dfs(0, "")
        return result

About your "how does this become backtracking?" note¶

This:

for i in ["a", "b", "c"]:
    for j in ["d", "e", "f"]:
        for k in ["g", "h", "i"]:
            combinations.append(i + j + k)

becomes:

choices = [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
]

result = []
path = []

def dfs(level: int) -> None:
    if level == len(choices):
        result.append("".join(path))
        return

    for ch in choices[level]:
        path.append(ch)
        dfs(level + 1)
        path.pop()

Idea:

• level says which loop depth you are at.
• The recursive call enters the next loop.
• The pop() is the backtracking step.

Why your iterative attempt misses "ad"¶

Your stack version mixes two different states into globals:

• current depth i
• current built string s

Those belong to each stack frame, but you keep only one shared i and one shared s.

So when you pop one branch and continue another, the string/depth restoration is incomplete, which skips combinations like "ad".

If you want iterative DFS, each stack item should carry the full state for that branch, for example:

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []
        stack = [(0, "")]  # (index in digits, built string)

        while stack:
            i, s = stack.pop()

            if i == len(digits):
                result.append(s)
                continue

            # Push in reverse so pop() processes letters in normal order.
            for ch in reversed(phone[digits[i]]):
                stack.append((i + 1, s + ch))

        return result

This works because every pending branch stores its own full state.

Extra¶

Complexity¶

Explain how you get this time complexity. I thought it would be \(O(4^n)\). I don't understand why we mutiply it by \(n\).

You are not missing much - the subtle part is what counts as work per result.

If you only count the shape of the recursion tree, then yes:

• Branching factor is at most 4
• Depth is n
• Number of leaves is about 4^n

So the tree itself suggests:

• \(O(4^n)\) recursive states/leaves, roughly

But to produce the actual answers, each answer is a string of length n, and building that string costs work.

Where the extra n comes from¶

In this version:

result.append("".join(path))

at every leaf:

• path has length n
• "".join(path) must copy n characters into a new string

So:

• number of leaves: up to \(4^n\)
• work per leaf to build the final string: \(O(n)\)

Therefore:

• total = \(O(n \cdot 4^n)\)

Why \(O(4^n)\) feels natural¶

Because the algorithm explores combinations like a tree:

• each digit gives up to 4 choices
• so total combinations is at most \(4^n\)

That is correct for:

• the number of outputs
• the number of leaves
• the recursion-tree growth up to constant factors

But if the output strings themselves must be constructed, the total runtime includes that cost too.

A concrete example¶

If n = 4 and every digit had 4 letters:

• number of combinations = \(4^4 = 256\)

Each combination has length 4, for example:

"apwz"
"apwx"
...

Even if finding each leaf were free, you still must write 4 characters per result.

So just materializing the outputs already costs:

• \(256 \cdot 4\)

That is the same pattern as:

• \(4^n \cdot n\)

Another way to see it¶

The output itself has size:

• number of strings: about \(4^n\)
• length of each string: \(n\)

So the total output size is:

• \(O(n \cdot 4^n)\)

An algorithm cannot be asymptotically faster than the size of the output it must return.

Why some people still say \(O(4^n)\)¶

Sometimes interview explanations simplify and say:

• "There are \(4^n\) combinations"

This is often used as a shorthand.

It is acceptable if they are focusing on:

• number of combinations generated

But the more precise runtime for returning all strings is:

• \(O(n \cdot 4^n)\)

Tiny nuance about your exact recursive version¶

If you build strings like this:

dfs(i + 1, s + ch)

then s + ch also creates a new string each time.

That means there is string-copying work not only at leaves, but along the path too.

Still, the usual clean complexity stated is:

• Time: \(O(n \cdot 4^n)\)
• Space: \(O(n)\) auxiliary, ignoring output

because the dominant idea is still:

• \(4^n\) results
• each result has length \(n\)

So your intuition of \(O(4^n)\) was close - it counts combinations, but not the cost of constructing each length-\(n\) answer.

Backtracking with iterative DFS¶

Write an iterative DFS solution that build a path like in DFS recursive instead of concatenating string at each step due to the use of the stack = [(0, "")] in your improvement above.

Yes - to mimic recursive DFS more closely, the stack should store enough state to let you:

• know which digit you are exploring
• know which choice you are trying next at that digit
• mutate one shared path
• backtrack with path.pop()

That is the iterative equivalent of the call stack.

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []
        path = []

        # Stack frame:
        # (digit_index, next_char_index_to_try_at_this_digit)
        stack = []
        i = 0

        while True:
            # Go down as far as possible, like recursive DFS.
            while i < len(digits):
                letters = phone[digits[i]]

                # We are about to choose letters[0] now.
                # If we come back later, we should resume from index 1.
                stack.append((i, 1))
                path.append(letters[0])
                i += 1

            # Reached a leaf: one full combination is built.
            result.append("".join(path))

            # Backtrack until we find a frame with another choice left.
            while stack:
                i, next_j = stack.pop()
                path.pop()

                letters = phone[digits[i]]
                if next_j < len(letters):
                    # Take the next choice at this level.
                    path.append(letters[next_j])

                    # If we come back again to this same level,
                    # continue from the following choice.
                    stack.append((i, next_j + 1))

                    # Then continue DFS on the next digit.
                    i += 1
                    break
            else:
                # No frame left: DFS is finished.
                return result

How to read it:

• path is the current partial answer, exactly like recursive backtracking.
• stack stores suspended frames, exactly like recursion would.
• each frame says:
  • which digit it belongs to
  • which letter index should be tried next when we return to that digit

What about using path list in iterative DFS non-backtracking?¶

Ok but can't we just replace (i, s) by (i, []) or something similar in the iterative DFS (non-backtracking)?

Yes, you can, but there is an important Python gotcha:

• if you put a mutable list in the stack,
• you must not reuse the same list object for multiple branches,
• otherwise all stack entries will point to the same path.

What goes wrong with (i, path_list)¶

This is wrong:

stack.append((i + 1, path))

because then:

• one branch modifies path
• all other branches see the same modification

So if you use lists in stack frames, each pushed branch needs its own copy.

Safe version with lists¶

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []

        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        result = []
        stack = [(0, [])]  # (index, path as list of chars)

        while stack:
            i, path = stack.pop()

            if i == len(digits):
                result.append("".join(path))
                continue

            for ch in reversed(phone[digits[i]]):
                stack.append((i + 1, path + [ch]))

        return result

This works because:

• path + [ch] creates a new list
• each stack entry owns its own partial path

But note the tradeoff¶

This does not behave like recursive backtracking with one shared path.

It behaves more like the string version:

• (i, s + ch)
• replaced by (i, path + [ch])

So:

• it is correct
• it is simple
• but it still copies the whole partial path at every push

Cost of that copying¶

If current path length is k, then:

path + [ch]

costs:

• \(O(k)\)

So this is not avoiding copying in the same way true backtracking does.

Difference from real backtracking¶

Stack-of-state approach¶

stack.append((i + 1, path + [ch]))

• every branch stores its own full partial path
• easy to write
• copies partial path many times

True backtracking approach¶

• one shared path
• append
• explore
• pop
• stack stores only control state

This is closer to recursive DFS and uses less temporary copying.

So the short answer¶

Yes, you can replace (i, s) with (i, path_list) if you do:

stack.append((i + 1, path + [ch]))

and not:

stack.append((i + 1, path))

But that is still a "copy-the-state-per-branch" solution, not a true iterative backtracking simulation with one shared path.

Tiny rule of thumb¶

• immutable state like s:
  • safe to store directly
• mutable state like path:
  • either copy it for each branch
  • or use one shared object and explicitly backtrack

That is the key distinction.

Backtracking is really about do -> recurse -> undo on shared state¶

Ok I get it.

So backtracking is really about do + (recurse / go deep one path) + undo with do/undo modifying the same state. Am I understanding correctly?

So, the stack version stack = [(0, "")] with a string is not backtracking because we merge two kind of state in one:

• do/undo state which build the thing we want
• (recurse / go deep one path) which traverses the graph

Am I correct?

In practice (real code base and LeetCode interview questions), is backtracking done with recursive DFS or imperative DFS? imperative DFS is a bit ugly but recursive DFS might overflow the stack.

Yes - that is the right idea.

Backtracking is usually:

• do
• go deeper
• undo

And the important part is:

• do and undo mutate the same shared state
• recursion or an explicit stack only controls where to return next

So your summary is good.

About the stack = [(0, "")] version¶

Yes, that version is usually DFS, but not really what people mean by backtracking.

Why:

• each branch carries its own independent state: s
• there is no shared mutable state to undo
• you do not need a real undo step

So it is better described as:

• iterative DFS over states

rather than:

• backtracking with shared state

Your distinction is correct¶

You said there are two kinds of state:

• traversal state
• constructed-solution state

That is exactly the useful mental model.

In recursive backtracking¶

These are separated:

• traversal state is handled by the call stack
• solution-building state is the shared path, modified by append/pop

In stack = [(i, s)]¶

They are bundled together:

• stack stores both where you are and what you built
• no undo is needed because every branch has its own copy

That is why it feels different.

Is backtracking recursive DFS or imperative DFS in practice?¶

Usually:

• recursive DFS

Most interview backtracking solutions are recursive because:

• shorter
• clearer
• matches the idea naturally
• easier to reason about

Typical interview examples:

• subsets
• permutations
• combinations
• N-Queens
• word search
• phone number letters

are almost always written recursively.

When would imperative DFS be used?¶

Usually when:

• recursion depth may be very large
• the language has a small recursion limit
• the team prefers explicit control
• you need to avoid call-stack risk

In Python specifically:

• recursion is elegant
• but deep recursion can hit the recursion limit

So for very deep traversals, iterative DFS is often safer.

For LeetCode / interviews¶

In practice:

• use recursive backtracking unless depth can be large

For this problem:

• digits.length <= 4

so recursive DFS is absolutely the normal and best answer.

No interviewer will prefer an iterative version here unless they explicitly ask for it.

Good rule of thumb¶

Use recursive backtracking when¶

• depth is small or moderate
• the problem is naturally "choose, explore, unchoose"
• clarity matters most

Use iterative DFS when¶

• depth can be huge
• recursion limit is a real risk
• you are doing plain graph/tree traversal more than "choose/unchoose"

One subtle point¶

People often use "backtracking" loosely to mean:

• DFS that explores possibilities

even if the code actually copies state per branch instead of mutating and undoing one shared state.

So in casual discussion:

• stack = [(i, s)] might still be called "backtracking"

But if you want the precise distinction:

• backtracking = shared mutable state + undo
• DFS over copied states = DFS/state-space search, but not strict choose-unchoose backtracking

Short answer¶

Yes, you understand it correctly.

• Backtracking is really about do -> recurse -> undo on shared state.
• Recursive DFS naturally handles traversal state.
• The (i, s) stack version is DFS over copied states, not true backtracking.
• In interviews and most real code for these problems, recursive DFS is the standard choice unless recursion depth is dangerous.