Letter Combinations of a Phone Number
For a number find all possible character subset could be possible
Letter Combinations of a Phone Number — Backtracking
Problem
Given a string containing digits from 2 to 9, return all possible letter combinations that the digits could represent.
Example:
Input:
"23"
Output:
[
"ad",
"ae",
"af",
"bd",
"be",
"bf",
"cd",
"ce",
"cf"
]
Solution
var letterCombinations = function(digits) {
let result = [];
if (!digits) {
return [];
}
const phoneMap = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
function backtrack(index, path) {
if (path.length === digits.length) {
result.push(path);
return;
}
for (const letter of phoneMap[digits[index]]) {
backtrack(index + 1, path + letter);
}
}
backtrack(0, '');
return result;
};
Main Idea
This is a backtracking problem.
The basic idea is:
For each digit, try every possible letter and recursively move to the next digit.
For example:
digits = "23"
2 → abc
3 → def
We need to choose:
one letter from "abc"
+
one letter from "def"
So:
a + d = ad
a + e = ae
a + f = af
b + d = bd
b + e = be
b + f = bf
c + d = cd
c + e = ce
c + f = cf
The Two Important Parameters
The recursive function is:
function backtrack(index, path)
It has two important pieces of information:
index → Which digit are we currently processing?
path → What combination have we built so far?
For example:
digits = "23"
index = 0
path = ""
means:
"I haven't processed any digit yet."
Later:
index = 1
path = "a"
means:
"I processed digit
2and chosea. Now I need to process digit3."
The Phone Map
const phoneMap = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
This represents the letters on a phone keypad.
For example:
2 → abc
3 → def
4 → ghi
5 → jkl
6 → mno
7 → pqrs
8 → tuv
9 → wxyz
Starting the Recursion
At the end of the function:
backtrack(0, '');
We start with:
index = 0
path = ""
For:
digits = "23"
this means:
digits
↓
"23"
↑
index = 0
We are currently processing digit 2.
Getting the Possible Letters
Inside the function:
for (const letter of phoneMap[digits[index]]) {
backtrack(index + 1, path + letter);
}
Initially:
index = 0
Therefore:
digits[index]
is:
digits[0] // "2"
Then:
phoneMap[digits[index]]
becomes:
phoneMap["2"]
which gives:
"abc"
So the loop effectively becomes:
for (const letter of "abc")
The loop will try:
a
b
c
First Choice: a
Initially:
index = 0
path = ""
The loop chooses:
letter = "a"
Then:
backtrack(index + 1, path + letter);
becomes:
backtrack(1, "a");
Now:
index = 1
path = "a"
We have chosen a letter for digit 2.
Processing the Second Digit
Now:
digits = "23"
↑
index = 1
So:
digits[index]
is:
digits[1] // "3"
Then:
phoneMap["3"]
gives:
"def"
So we now try:
d
e
f
Choose d
Current state:
index = 1
path = "a"
Choose:
letter = "d"
Then:
backtrack(2, "ad");
Now:
index = 2
path = "ad"
The Base Case
We have:
if (path.length === digits.length) {
result.push(path);
return;
}
Our values are:
path.length = 2
digits.length = 2
Therefore:
2 === 2
is true.
So:
result.push("ad");
The result becomes:
[
"ad"
]
Then we return.
Choosing e
We return to:
index = 1
path = "a"
The loop continues.
Now:
letter = "e"
So:
backtrack(2, "ae");
The base case is reached:
"ae".length === "23".length
Therefore:
result.push("ae");
Result:
[
"ad",
"ae"
]
Choosing f
The same thing happens:
path = "a"
letter = "f"
Call:
backtrack(2, "af");
Result:
[
"ad",
"ae",
"af"
]
Now all possibilities starting with a are complete.
Going Back and Choosing b
The function returns to:
index = 0
path = ""
The first loop continues.
It now chooses:
b
So:
backtrack(1, "b");
Then the second digit can choose:
d
e
f
Giving:
bd
be
bf
Choosing c
Finally:
c
is chosen for the first digit.
The second digit again gives:
d
e
f
Producing:
cd
ce
cf
Complete Recursion Tree
The whole process can be visualized as:
""
/ | \
a b c
/ | \ / | \ / | \
d e f d e f d e f
| | | | | | | | |
ad ae af bd be bf cd ce cf
Every path from the top to the bottom represents one complete combination.
Why path + letter?
The important line is:
backtrack(index + 1, path + letter);
Suppose:
path = "a"
letter = "d"
Then:
path + letter
becomes:
"ad"
So we pass:
backtrack(2, "ad");
This means:
"I've chosen
d. Add it to my current combination and move to the next digit."
Why Don't We Need to Undo path?
In the permutation problem, we had to do:
// choose
swap();
// explore
backtrack();
// undo
swap();
because we were modifying the same array.
Here, we're doing:
backtrack(index + 1, path + letter);
path + letter creates a new string.
For example:
path = "a"
path + "d" = "ad"
The original path is still:
"a"
It wasn't modified.
So there is no need to explicitly undo anything.
Compare With Permutations
Permutations
In permutations, we modify the original array:
[nums[start], nums[i]] = [nums[i], nums[start]];
Therefore we need:
Choose
↓
Explore
↓
Undo
Example:
// Choose
swap();
// Explore
generatePermute(start + 1);
// Undo
swap();
Letter Combinations
Here we don't modify path.
Instead:
path + letter
creates a new string.
So:
Choose
↓
Create new path
↓
Explore
There is no explicit undo.
What Does index Represent?
For:
digits = "23"
the recursion progresses like this:
index = 0
↓
process "2"
index = 1
↓
process "3"
index = 2
↓
finished
So:
index = current digit
What Does path Represent?
path represents the combination we've built so far.
For example:
path = ""
Nothing chosen.
Then:
path = "a"
One letter chosen.
Then:
path = "ad"
Two letters chosen.
Once:
path.length === digits.length
the combination is complete.
The Three Important Parts
Remember these three things:
index → Where am I?
path → What have I built?
loop → What choices can I make?
For example:
function backtrack(index, path) {
// Is the combination complete?
if (path.length === digits.length) {
result.push(path);
return;
}
// What choices do I have?
for (const letter of phoneMap[digits[index]]) {
// Choose the letter and move forward
backtrack(index + 1, path + letter);
}
}
The Backtracking Pattern
The general pattern here is:
Start
|
What choices?
|
+--------+--------+
| | |
A B C
| | |
Explore Explore Explore
| | |
Done Done Done
In code:
for (const choice of choices) {
backtrack(nextIndex, currentPath + choice);
}
One-Sentence Mental Model
Think of the algorithm as:
For each digit, try every possible letter, add that letter to the current path, move to the next digit, and save the path when every digit has been processed.
Or even shorter:
Choose → Move Forward → Complete → Save
Complexity
If there are n digits and each digit has up to 4 letters, there can be up to:
4^n
combinations.
For example:
"23"
3 × 3 = 9 combinations
For:
"79"
we have:
4 × 4 = 16 combinations
So the number of generated combinations is:
O(4^n)
The output itself also takes space proportional to the number and length of the combinations.
Final Mental Picture
For:
digits = "23"
think:
""
/ | \
a b c
/|\
d e f
Then repeat the same
"d e f" choices for b and c.
Result:
ad ae af
bd be bf
cd ce cf
The important recursive line:
backtrack(index + 1, path + letter);
means:
"I've chosen this letter. Add it to my combination and solve the next digit."
That is the core of this backtracking solution.