代码随想录算法训练营Day19 | 77.组合、216.组合总和|||、17.电话号码的字母组合

回溯问题的模板

    public static void backtracking(参数列表){
        if(终止条件){
        	存放结果
            return;
        }

        for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
        	处理节点;
        	backtracking(路径，选择列表); // 递归
       		回溯，撤销处理结果
        }
    }

LeetCode 77 组合

本题思路：组合问题，利用回溯来解决。回溯就是用来解决纯暴力解决不了的问题。此题，如果通过 for 循环, 也可以解决，但是如果 k 越来越来越大，那么就要写越来越多的 for，不切实际。
此时就可以利用回溯来解决。

• 第一步就是分析终止条件，终止条件，就是组合大小等于 k，就可以进行结束，进行保存
• 而 for 循环处理的就是这每一个元素
  • 保存节点
  • 然后进行递归处理
  • 然后回退到上一个节点

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        backtracking(path,res,n,k,1);
        return res;
    }

    public void backtracking(List<Integer> path,List<List<Integer>> res,int n, int k, int startIndex){
        // 先找出口终止条件
        if(path.size() == k){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex; i <= n-(k-path.size())+1 ; i++){
            path.add(i);
            backtracking(path,res,n,k,i+1);
            path.removeLast();
        }
    }
}

LeetCode 216 组合总和||

本题思路：和上题一样，终止条件也是元素个数满足为 k的时候，不过保存结果的时候，要加个判断，和是否等于 n，只有等于才会保存起来。

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        backtracking(res,path,k,n,1);
        return res;
    }


    public void backtracking(List<List<Integer>> res, List<Integer> path, int k , int n , int startIndex){
        // 终止条件
        if(path.size() == k){
            int sum = 0;
            for(int i = 0; i < path.size(); i++){
                sum += path.get(i);
            }
            if(sum == n){
                res.add(new ArrayList(path));
            }
        }
        for(int i = startIndex; i <= 9; i++){
            path.add(i);
            backtracking(res,path,k,n,i+1);
            path.removeLast();
        }
    }
}

LeetCode 17 电话号码的字母组合

本题思路：本题和上述两题不同，不在同一个集合里面，是不同的集合，所以参数就用 index 了，不用 startIndex 进行去重。

• 首先要将数字和对应的字符做一个映射
• 这里终止条件就是遍历完当前数字所对应的字符串了

class Solution {

    String[] sMap = new String[]{" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList();
        List<Character> path = new ArrayList();
        if(digits.equals("")){
            return res;
        }
        backtracking(digits,0,res,path);
        return res;
    }

    public void backtracking(String digits, int index, List<String> res, List<Character> path){
        // 终止条件
        if(index == digits.length()){
            StringBuilder s =  new StringBuilder();
            for(int i = 0; i < path.size(); i++){
                s.append(path.get(i));
            }
            res.add(s.toString());
            return;
        }
        Character ch = digits.charAt(index);
        String str = sMap[ch - '0'];
        for(int i = 0; i < str.length(); i++){
            path.add(str.charAt(i));
            backtracking(digits,index+1,res,path);
            path.removeLast();
        }
    }
}