回溯算法

回溯的本质是穷举，所以不是高效的算法
回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
注意区分一个集合取组合和多个集合取组合的细节。
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
需要注意问题是有一个解还是多个解，一个解的需要返回值，一旦找到解就逐级返回，多个解的不需要返回值

因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

77、组合

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        int index = 1;
        travesal(n,k,index);
        return result;
    }
    public void travesal(int n, int k, int index){
        // 终止条件，得到k个数的组合
        if(temp.size() == k){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
            temp.add(i);
            travesal(n,k,i+1);//递归
            temp.remove(temp.size() - 1);//回溯
        }
    }
}

216、组合总和 III

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<>();
    public int sum;
    public List<List<Integer>> combinationSum3(int k, int n) {
        sum = 0;
        find(k,1,n);
        return result;
    }
    public void find(int k, int left, int right){
        if(temp.size() == k){
            if(sum == right){
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        for(int i = left; i <= 9 - (k - temp.size()) + 1; i++){
            if(sum > right){
                continue;
            }
            temp.add(i);
            sum += i;
            find(k,i+1,right);
            sum -= temp.get(temp.size() - 1);
            temp.remove(temp.size() - 1);
            
        }
    }
}

17、电话号码的字母组合

class Solution {
    public List<String> result = new ArrayList<String>();
    public StringBuffer str = new StringBuffer();
    public List<String> letterCombinations(String digits) {
        // 边界条件
        if(digits == null || digits.length() == 0){
            return result;
        }
        char[] digitsArr = digits.toCharArray();
        // 映射关系
        String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int index = 0;
        letterCombinationsHelper(digitsArr, find, index);
        return result;
    }
    public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
        if(index == digitsArr.length){
            result.add(new String(str));
            return;
        }
        // 第index个数字对应的字母
        String strTemp = find[digitsArr[index] - '0'];
        for(int i = 0; i < strTemp.length(); i++){
            str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个
            letterCombinationsHelper(digitsArr,find,index+1);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

39、组合总和

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int sum = 0;
        int index = 0;
        Arrays.sort(candidates);
        combinationSumHelper(candidates,index,sum,target);
        return result;
    }
    public void combinationSumHelper(int[] candidates, int index, int sum,int target){
        if(sum >= target){
            if(sum == target){
                result.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        for(int i = index; i < candidates.length; i++){
            sum += candidates[i];
            temp.add(candidates[i]);
            combinationSumHe