Introduction

Have you ever wondered how a phone number can represent multiple possible words? On a traditional telephone keypad, each digit from 2 to 9 is associated with three or four letters. For example, 2 represents a, b, and c, while 3 represents d, e, and f.

Now imagine entering the digits "23". For every letter represented by 2, we can combine it with every letter represented by 3. This produces nine possible combinations, including "ad", "ae", "af", "bd", and "cf".

This is the central idea behind LeetCode 17: Letter Combinations of a Phone Number. The challenge is to generate every possible combination without missing any valid result.

In this article, we will explore a recursive Java solution, understand how the keypad mapping is built, and trace how the recursive calls generate the final list.

Problem link: LeetCode 17 — Letter Combinations of a Phone Number

Understanding the Problem

You are given a string digits containing numbers from 2 to 9. Each digit corresponds to a group of letters on a telephone keypad.

Your task is to return all possible strings that can be formed by choosing exactly one letter for each digit.

For example, if the input is "23":

1. Digit 2 can contribute a, b, or c.
2. Digit 3 can contribute d, e, or f.
3. Each letter selected from the first group must be paired with every letter in the second group.

The resulting combinations are:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

The order of the returned combinations does not matter.

One important detail is that the digits 0 and 1 are not included in the input constraints because they do not map to letters in this problem.

Approach: Recursion with Phone Keypad Mapping

The key observation is that each digit represents a choice, and recursion explores every available choice at the current position.

For example, when processing "23", we first select a letter from digit 2. After that, we move to digit 3 and try all its letters. Once we have selected one letter for each digit, we have completed a valid combination.

Our solution uses three main components.

1. Build the digit-to-letter mapping

We create a list of character lists called arr.

Each position represents a digit, and the corresponding list contains its letters. For instance:

1. arr.get(2) contains a, b, c.
2. arr.get(3) contains d, e, f.
3. arr.get(7) contains p, q, r, s.
4. arr.get(9) contains w, x, y, z.

We begin with two empty lists at indices 0 and 1, so the mapping for a digit can be accessed directly using its numeric value.

The variable charnum starts at 97, the ASCII value of lowercase a. We convert consecutive numeric values into characters and advance the counter by three or four letters, depending on the digit.

This lets us construct the entire keypad mapping programmatically rather than writing each group manually.

2. Recursively build each combination

The helper method sol() receives four parameters:

1. arr: the phone keypad mapping.
2. ind: the current position in the input string.
3. dig: the original digit string.
4. sb: the combination constructed so far, represented as a string.

At each recursive call, we examine the current digit and iterate over its available letters.

For every letter, we make another recursive call with that letter appended to the current combination. This continues until every digit has contributed one letter.

3. Stop when a complete combination is formed

The base condition is:

if (sb.length() == dig.length())

When the constructed string has the same length as the input digit string, we have selected one letter for every digit. We add that combination to the result list and return from the current call.

The recursive process then continues exploring the remaining choices.

This is the essential stopping condition that prevents the recursion from continuing beyond the number of input digits.

Java Solution

Here is the recursive solution, preserving your approach while making two small improvements:

1. Use a StringBuilder when adding a letter instead of repeatedly creating intermediate strings.
2. Handle an empty input and keep the result list local to the method, so repeated calls do not accidentally reuse results from a previous invocation.

Why use StringBuilder and remove the last character?

Your original code uses sb + arr.get(...).get(i) to create a new string for each recursive call. This is valid Java, but repeated string concatenation creates additional string objects.

The improved version modifies a single StringBuilder:

1. append(ch) adds the chosen letter.
2. The recursive call explores the combinations that begin with that letter.
3. deleteCharAt(sb.length() - 1) removes the letter after returning, allowing the next letter to be tried.

This pattern is called backtracking. We make a choice, explore its consequences, and undo the choice before exploring another branch.

It is especially useful when generating permutations, combinations, subsets, and other possible arrangements.

Dry Run: digits = "23"

Let's trace the recursion to see exactly how the combinations are generated.

Initially, the current string is empty, and the current index is 0.

The process follows this sequence:

1. Select a from digit 2.
2. Explore all choices from digit 3, producing ad, ae, and af.
3. Return to the first digit and replace a with b.
4. Explore digit 3 again, producing bd, be, and bf.
5. Repeat with c, producing cd, ce, and cf.

The final result contains nine combinations.

Why nine? The first digit has three choices, and the second digit also has three choices. Therefore, the total number of combinations is 3 × 3 = 9.

Complexity Analysis

Let n be the length of the input string, and let R be the total number of generated combinations.

Every digit has either three or four possible letters. The maximum number of combinations is therefore 4^n.

Time complexity: O(n × R)

There are R complete combinations, each containing n characters. Constructing and storing all these strings requires O(n × R) total time. Since R can be as large as 4^n, the worst-case time complexity is O(n × 4^n).

Auxiliary space complexity: O(n)

The recursion depth is at most n, and the StringBuilder holds at most n characters. The keypad mapping contains a fixed number of letters, so its space usage is constant with respect to the input length.

Output space: O(n × R)

The result list stores R strings, each of length n. This output memory is separate from the auxiliary space used by the algorithm.

Because the constraints limit the input to at most four digits, the number of generated combinations remains small.

Common Mistakes to Avoid

1. Forgetting to advance to the next digit

Every recursive call must process the next position. If the index is not incremented, recursion will keep processing the same digit.

2. Using an incorrect base condition

The recursion should stop after processing all digits. Checking whether the current string has the same length as the input works, but checking ind == digits.length() directly makes the relationship between the index and the stopping condition clearer.

3. Forgetting to undo a choice

When using a shared StringBuilder, remember to remove the character after the recursive call. Otherwise, letters from one branch may incorrectly carry over into another.

4. Reusing a result list across separate calls

In your original implementation, lis is a class-level field. If the same Solution instance is used for multiple calls, previous results can remain in the list. Creating the result list inside letterCombinations() avoids this issue.

5. Ignoring empty input

The provided constraints guarantee at least one digit, but returning an empty list for an empty input is a useful defensive behavior. It also avoids accidentally treating the empty string as a valid result.

Interview Tip: Recognize the Backtracking Pattern

Whenever a problem asks you to generate every possible arrangement from several groups of choices, consider recursion or backtracking.

A useful way to design the solution is to ask:

1. What choices are available at the current position?
2. What state should be passed to the next recursive call?
3. When is a complete answer formed?
4. What needs to be undone before exploring the next choice?

For this problem, the choices are the letters associated with the current digit, the state is the current combination and digit index, and a complete answer is reached after processing all digits.

The same reasoning can help with problems such as generating subsets, permutations, combination sums, and other recursive search problems.

Conclusion

LeetCode 17, Letter Combinations of a Phone Number, is a useful introduction to recursive backtracking in Java. The phone keypad gives us a set of choices for every digit, and recursion explores every possible sequence of those choices.

The most important part is not the keypad mapping itself. It is learning how to explore one choice completely, return to the previous state, and then try the next choice without mixing results between branches.

Once this pattern becomes familiar, many combination-generation problems become easier to approach and explain in coding interviews.

Key takeaway: Build the keypad mapping, choose one letter per digit, stop when every digit has been processed, and backtrack to explore the remaining possibilities.