No.1

题目

思路

回溯法

递归分析

全局变量：path存储临时路径、result存储结果
返回值：空，参数：k，n，start表示从[1, 9]之间哪个数开始
终止条件：发现凑够k个数，判断值等于n，就放入结果集
单层递归逻辑：处理当前节点，递归，回溯

代码

List<List<Integer>> result = new ArrayList<>();  
LinkedList<Integer> path = new LinkedList<>();  
  
public void combineHelper(int k, int n, int start, int sum) {  
    if (path.size() == k && sum == n) {  
        result.add(new ArrayList<>(path));  
        return;  
    }  
  
    for (int i = start; i <= 9; i++) {  
        path.add(i);  
        combineHelper(k, n, i + 1, sum + i);  
        path.removeLast();  
    }  
}  
  
public List<List<Integer>> combinationSum3(int k, int n) {  
    combineHelper(k, n, 1, 0);  
    return result;  
}

No.2

题目

电话号码的字母组合

思路

回溯法
数字和字母映射
不能在类成员写Map<Character, String> map = new HashMap<>(){{map.put(K, V)}};Leetcode报空指针异常

递归分析

全局变量：path，result
返回值：空，参数：digits，index记录遍历第几个数字了
终止条件：index 等于输入的数字个数（digits.size）了，收集结果，结束本层递归。
单层递归逻辑：取index指向的数字，并找到对应的字符集；for循环来处理这个字符集；

代码

List<String> result = new ArrayList<>();  
StringBuilder path = new StringBuilder();  
Map<Character, String> map = new HashMap<>();  
public void combineHelper(String digits, int index) {  
    if (index == digits.length()) {  
        result.add(path.toString());  
        return;  
    }  
  
    char digit = digits.charAt(index);  
    String letters = map.get(digit);  
    for (int i = 0; i < letters.length(); i++) {  
        path.append(letters.charAt(i));  
        combineHelper(digits, index + 1);  
        path.deleteCharAt(path.length() - 1);  
    }  
}  
  
public List<String> letterCombinations(String digits) {  
    if (digits.length() == 0)  
        return result;  
      
    map.put('2', "abc");  
    map.put('3', "def");  
    map.put('4', "ghi");  
    map.put('5', "jkl");  
    map.put('6', "mno");  
    map.put('7', "pqrs");  
    map.put('8', "tuv");  
    map.put('9', "wxyz");  
  
    combineHelper(digits, 0);  
    return result;  
}