**216. 组合总和 III（基础回溯算法）**

List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int k, n;
public List<List<Integer>> combinationSum3(int _k, int _n) {
    k = _k;
    n = _n;
    // 上一个数是0，目前已经有0个数，求和是0
    dfs(0, 0, 0);
    return ans;
}

void dfs(int x, int cur, int sum) {
    if(cur == k) {
        if(sum == n) ans.add(new ArrayList<>(list));
        return;
    }
    for(int i = x + 1; i < 10; i++) {
        // 依次尝试选择每个数字
        list.add(i);
        dfs(i, cur + 1, sum + i);
        list.remove(list.size() - 1);
    }
}

**17. 电话号码的字母组合（回溯算法练习）**

String map[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> list = new ArrayList<>();

public List<String> letterCombinations(String digits) {
    for(char c: digits.toCharArray()) {
        dfs(c);
    }
    return list;
}
public void dfs(char c) {
    if(list.isEmpty()) {
        for(Character ch: map[c-'2'].toCharArray()) {
            list.add(ch.toString());
        }
    }else {
        int n = list.size();
        for(int i = 0; i < n; i++) {
            String tmp = list.get(0);
            for(Character ch: map[c-'2'].toCharArray()) {
                list.add(tmp+ch.toString());
            }
            list.remove(0);
        }
    }
}