n叉树的遍历，用递归非常简洁！

### 题目

Given a digit string, 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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].


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

### 迭代回溯算法 $O(3^n)$

[""]


[a,b,c]


[ad,ae,af,b,c]


[ad,ae,af,bd,be,bf,c]


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


#### 代码

public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) { return result; }
for (int i = 0; i < digits.length(); i++) {
int digit = digits.charAt(i)-'0';
ListIterator<String> ite = result.listIterator();
while (ite.hasNext()) {
String old = ite.next();
ite.remove();
for (int j = 0; j < letters.length(); j++) {
}
}
}
return result;
}
}


#### 也可以这样写

public List<String> letterCombinations(String digits) {
String[] mapping = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for(int i =0; i<digits.length();i++){ // 这行非常帅
int x = Character.getNumericValue(digits.charAt(i));
while(ans.peek().length()==i){
String t = ans.remove();
for(char s : mapping[x].toCharArray())
}
}
return ans;
}


### 回溯算法，递归版

#### 代码

public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) { return result; }
return result;
}
public void letterCombinationsRecursive(List<String> list, String str, String[] letterPad, int index, String digits) {
if (index == digits.length()) { list.add(str); return; }
for (char c : letterPad[digits.charAt(index)-'0'].toCharArray()) { // 当前按键上每个字母都是一条路
}
}
}