Why it works
- Call i chooses the letter for digit i and hands the rest to call i + 1, so the tree has one level per digit and one branch per letter: every word is one path from the root to a leaf.
- Removing the letter after the call comes back frees its place, so the next letter of the same digit is tried with the same letters before it.
- A word is saved only when i reaches the end, so it always has exactly one letter per digit.
Complexity
Time O(n × 4ⁿ) for n digits: up to 4ⁿ words, each joined in n steps. Memory O(n) besides the answer: the path and the call stack are n deep.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗