Backtracking
When the branching factor comes from the data
Nothing new in the search. The choices at each level are looked up rather than computed.
Key idea
Each level has its own option set
So far each level chose from the same pool. Some problems give a different set of options per level, supplied by a lookup table keyed on the input.
The search is unchanged. The only difference is where the loop gets its choices, and the depth of the recursion is the length of the input rather than a fixed size.
Edge cases
The empty input is a decision, not an accident
With no guard, an empty input reaches the base case immediately and produces one result: the empty string. Whether that is correct depends on the problem, and most versions of this want an empty list instead.
Handle it explicitly at the top rather than letting the recursion decide. An empty input producing exactly one empty result is the single most common failing test case in this family.
Cost
The cost is a product
The number of results is the product of the option counts across all levels. With b options at each of n levels that is b to the n, and each result costs O(n) to build.
So the answer is O(n times b to the n). Naming the base and the exponent separately, rather than saying exponential, is what a complexity question here is looking for.
Tip
The iterative alternative
This shape also has a clean non-recursive form: start with a list holding one empty string and, for each input character, replace the list with every existing entry extended by every option.
It is short and easy to explain, and it allocates more because each round rebuilds the whole list. Worth knowing as the answer to what if you could not use recursion, which is a common follow-up.
Predict the output: where the size of the answer comes from
Each level of the search draws its choices from a table keyed on the input. Type the three lines it prints.
Letter Combinations Of A Phone Number
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.