Day25｜回溯算法part02：216.组合总和III、17.电话号码的字母组合

216. 组合总和III

自己写的未剪枝版本：

class Solution {
    private List<List<Integer>> resList = new ArrayList<>();
    private List<Integer> res = new ArrayList<>();

    private void backtracing(int k , int n, int startIndex,int sum){
        if(sum == n && res.size() == k){
            resList.add(new ArrayList<>(res));
            return;
        }
        for(int i = startIndex; i <= 9; i++){
            res.add(i);
            sum += i;
            backtracing(k , n, i + 1, sum);
            sum -= i;
            res.remove(res.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracing(k , n, 1, 0);
        return resList;
    }
}

• 不知道为何已经超过100%的人了，但java剪枝仍然是重点。
• 集合固定的就是9个数[1,…,9]，所以for循环固定i<=9

剪枝(最好不在for循环中剪枝）

• 函数开头添加sum>n的条件就break，不然只会越加越大：

if(sum > n){
          return;
      }
if(res.size() > k){
                return;
      }
for(int i = startIndex; i <= 9; i++{
      res.add(i);
      sum += i;
      //            sum += i;
            backtracing(k , n, i + 1, sum + i);
//            sum -= i;
  }

（注意sum+i的位置）

• res的个数超过k也break，不然不符合条件了。
• 直接讲sum+i写入函数参数中，实际上也是一种回溯。

17. 电话号码的字符组合

• 自己的未剪枝版本：

class Solution {
    private List<String> resList = new ArrayList<>();
    private StringBuilder sb = new StringBuilder();

    private Map<Character, List<Character>> alphabet = new HashMap<>();

    void buildAlphabet(){
        alphabet.put('2', Arrays.asList('a','b','c'));
        alphabet.put('3', Arrays.asList('d','e','f'));
        alphabet.put('4', Arrays.asList('g','h','i'));
        alphabet.put('5', Arrays.asList('j','k','l'));
        alphabet.put('6', Arrays.asList('m','n','o'));
        alphabet.put('7', Arrays.asList('p','q','r','s'));
        alphabet.put('8', Arrays.asList('t','u','v'));
        alphabet.put('9', Arrays.asList('w', 'x','y','z'));
    }
    void backtracking(String digits, int startIndex){
        if(sb.length() == digits.length()){
            if(sb.toString().length() > 0){
                resList.add(sb.toString());
            }

            return;
        }
            for(int i = 0; i < alphabet.get(digits.charAt(startIndex)).size(); i++){
                sb.append(alphabet.get(digits.charAt(startIndex)).get(i));
                backtracking(digits, startIndex + 1);
                sb.setLength(sb.length() - 1);
            }

    }

    public List<String> letterCombinations(String digits) {
        buildAlphabet();
        backtracking(digits, 0);
        return resList;
    }
}

• 用一个字典存表；
• java的String不可改，用StringBuilder代替；
• 注意for循环中每个参数代表的集合空间中的意思。
• i：遍历对应数字的字母列表的长度，比如2就是abc为3；
• startIndex：遍历的字符串的目前在哪一位上；
• 换成之前的组合问题，i就相当于1～9，startIndex就是遍历到第几个位置的数了。