Letter Combinations

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

def letter_combinations(digits):
    out = []
    def go(i, path):
        if i == len(digits):
            out.append(''.join(path))   # save
            return
        for ch in KEYS[digits[i]]:
            path.append(ch)             # append
            go(i + 1, path)             # recurse
            path.pop()                  # pop
    if digits:
        go(0, [])
    return out

Letter Combinations of a Phone Number. On a phone keypad, the digits two to nine each carry three or four letters. Given some digits, return every string their letters could spell.

Take two, three. Two has A, B, C; three has D, E, F. Pair each letter of two with each letter of three: A D, A E, A F, and so on, up to C F. Nine strings.

For exactly two digits, two nested loops would work. But four digits need four loops, and the length isn't fixed.

So backtrack. Fill one position at a time: try each letter on that digit's key, append it, fill the rest the same way, then pop it and try the next. A full string is one answer.

Draw it as a tree: the first digit branches three ways, and each branch splits three more. Nine leaves, nine strings.

In code, a helper takes the position and the path. If the path is full, save it. Otherwise, for each letter: append, recurse, pop.

Let's dial two, three. A, then D: save A D. Pop, try E: A E. Then A F. Back up to B: B D, B E, B F. Then C D, C E, C F. Nine strings.

With up to four letters a key, there are up to four to the n strings, each n long, so the time is n times four to the n. Two, three, four gives twenty seven. The recursion is only n deep.

Press a key, try each letter, back up, try the next. That's Letter Combinations.