Remember the old keypads where each number had 2-3 letters associated with it. Given a string containing numbers form 2 to 9, find out all the possible word that string of numbers could mean.
numbers = "23" ans = ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
We can easily think of this problem in terms in sub-problems.
If we have all the word combinations available to us for the first n-1 digits, then for the nth digit, we just need to append all the characters corresponding to the nth digit to each one of them.
Using the above idea we can think of a recursive solution.
1. For a given string containing numbers.
2. Handle the base recursion cases.
3. For a string having only 1 digit, each individual character is the return value.
4. For each character at position n, get the return value from the position n-1, and append all the characters corresponding to the digit at n, 1 by 1.
5. Return this value as the answer.