Every position of the answer is a slot. Slot 0 comes from digits[0], slot 1 comes from digits[1], and so on. Each slot has its own list of options. For the digit 2 the options are a, b, c. For the digit 3 they are d, e, f.

backtrack(index) works on slot index only. It loops over keypad[digits[index]]. For each letter it does three things: path.append(letter), then backtrack(index + 1), then path.pop(). The append is the choice, the recursive call fills the later slots, and the pop undoes the choice.

Example: digits = "23". backtrack(0) appends a, so path = ['a']. backtrack(1) appends d, so path = ['a', 'd']. Now index == 2 == len(digits), so "ad" is saved. The pop removes d. The loop then appends e, and "ae" is saved, and so on.

After the three letters of slot 1 are done, backtrack(1) returns. The pop removes a from slot 0, and the loop appends b. The strings come out in this order: ad, ae, af, bd, be, bf, cd, ce, cf. That is 9 strings, which is 3 times 3.

The invariant is len(path) == index in every call. The path always holds one option for each slot before index, and no option for the slots from index onward.

A full combination is one option for each slot. In the recursion, slot 0 picks first, then slot 1, and so on. Two different combinations differ in at least one slot. At the first slot where they differ, the loop took a different letter, so they come from different branches.

No branch is ever cut. No choice in one slot limits the options of another slot. So every branch reaches index == slots, and every full combination appears. The number of saved strings is the product of the option counts of the slots.

I checked this with the card's code on 500 random digit strings. The saved strings were the same as itertools.product gives, in the same order. For "79" the result has 16 strings, because 7 and 9 have 4 options each.

This is the difference from Combinations (LC 77). There, all choices come from one shared pool, and an item cannot be used twice. Here, the slots do not share options, so there is no start index and no used set.

Let G be the number of full combinations. Each one is built in slots appends. Saving a copy with list(path) or "".join(path) costs slots as well. So the time is O(slots * G * T), where T is the cost of one choices call. The blueprint states this.

For the phone number, a slot has at most 4 options, so G is at most 4^N and the time is O(N * 4^N). The space is O(N) for path and the recursion stack. The saved strings are the output and are not counted.

The number of backtrack calls is smaller than the cost of saving. For 3 slots with 3 options each, I counted 40 calls. That matches (3^4 - 1) / 2 = 40.

The output is the cost. If the answer has G strings, no method can be faster than writing them. So the card has no pruning step to add.

Letter Case Permutation (LC 784): each character of s is a slot. A letter has two options, its lower case and its upper case. A digit has one option, itself. For s = "a1b2" the result is a1b2, a1B2, A1b2, A1B2.

Brace Expansion (LC 1087): each plain letter is a slot with one option, and each brace group is a slot with the listed options. Sort the options of a group first, because the answer must be in sorted order. For {a,b}c{d,e}f the result is acdf, acef, bcdf, bcef.

In both problems only the function choices(index) changes. The saving rule and the choose, recurse, undo loop stay the same.

One edge case: an empty slot gives no full combination, so the result is []. LeetCode's Letter Combinations of a Phone Number (LC 17) also asks for [] when digits is empty. The loop alone would return [""] for that input, so a solution must handle an empty digits before it starts.