# Find all possible combinations of words formed from mobile keypad

Given a sequence of numbers between [2-9], print all possible combinations of words formed from mobile keypad have some digits associated with each key.

Input: [2, 3, 4]

Output:

ADG BDG CDG AEG BEG CEG AFG BFG CFG ADH BDH CDH AEH BEH
CEH AFH BFH CFH ADI BDI CDI AEI BEI CEI AFI BFI CFI

We can use Recursion to solve this problem. The idea is to consider every input digit one by one, replace the digit with each character in the mobile keypad and recurse for the next digit. When all the digit are processed, we print the result.

Below is C++ and Java implementation of the idea –

## Java

Output:

ADG BDG CDG AEG BEG CEG AFG BFG CFG ADH BDH CDH AEH BEH CEH AFH BFH CFH ADI BDI CDI AEI BEI CEI AFI BFI CFI

##### Iterative implementation –

We can also solve this problem iteratively using a vector. The idea remains the same but instead of recursing, we push the partial-word into the vector. For each character associated with current digit in the keypad, we append the character to each word in the output list and push the result to the vector. So at the end of each iteration, vector contains all possible combinations of words till current digit. We repeat this process until all digits are processed.

Below is C++ and Java implementation of the idea –

## Java

Output:

[ADG, BDG, CDG, AEG, BEG, CEG, AFG, BFG, CFG, ADH, BDH, CDH, AEH, BEH, CEH, AFH, BFH, CFH, ADI, BDI, CDI, AEI, BEI, CEI, AFI, BFI, CFI]