Reference: LeetCode EPI 15.2

Difficulty: Medium

My Post: Java Solution Backtracking with Comments

## Problem

Given a string containing digits from

`2-9`

inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that $1$ does not map to any letters.

**Note:** Although the above answer is in lexicographical order, your answer could be in any order you want.

**Example:**

1 | Input: "23" |

**Follow up:** Consider no duplicate combinations.

## Analysis

### Backtracking

1 | // a simple mapping |

**Time:** $O(N \times 4^N)$ including string construction with $O(N)$ time at most.**Space:** $O(N \times 4^N)$

### No Duplicate Combinations

Use the idea of start index in Subsets II. This time we does not pass down the information of whether we pick or do not pick, but the start index as a more general approach.

1 | /* |

**Time:** $O(N \times 4^N)$**Space:** $O(N \times 4^N)$