Find all letter Combinations of a Phone Number
whenever you encounter a task where you have to combine or permute things, then backtracking is a possible approach.


True. It is not necessarily the best though (in fact it is rarely the best).

In this particular case, the problem naturally maps to finding the next combination. In turn, it is no more than an increment of a number in some fancy numbering system. In your example, the minimal possible string is ad. Subsequent increments yield ae, then af, then ('f' + 1 is d and a carry bit does carry) bd, etc.

Consider implementing the increment/next method directly. The space complexity will definitely benefit; and it is trivial to convert into a generator. The time complexity is likely to also benefit, depending on the use case.

PS: thank you for posting your train of thoughts.