Reference: LeetCode EPI 15.2
Difficulty: Medium

## 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:

Follow up: Consider no duplicate combinations.

## Analysis

### Backtracking

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.

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.