0 写在前面

回溯法：n叉不等高度数的完全遍历，明确树的下一个分支宽度与树的高度。

对于宽度：这个体现在回溯法模板的for循环里面

对于高度：体现在回溯法遍历结束的终止条件里面

这两个的核心思想如下:

1. 排列问题要搞一个visited数组标记已经访问的
2. 组合问题要维护好一个起始的索引

1 排列问题 - 全排列

LeetCode 46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

1.1 树的确定

• 宽度：每一层都要遍历一下数组的每一个数字，那么树的宽度是nums.length，这个体现在回溯法模板的for循环里面
• 高度：当前的临时list长度为数组长度，结束

1.2 排列：维护一个visited数组

回溯时也得同步这个visited数组

1.3 代码

class Solution {

    public void backTrack(List<List<Integer>>ans,List<Integer>temp,int[]visited,int[]nums){
        if(temp.size()==nums.length){
            ans.add(new ArrayList<>(temp));
            return ;
        }
        //回溯法
        for(int i = 0;i<nums.length;i++){
            //没有遍历过
            if(visited[i]==0){
                temp.add(nums[i]);
                visited[i] = 1;
                //遍历树的下一层就好
                backTrack(ans,temp,visited,nums);
                //回溯
                temp.remove(temp.size()-1);
                visited[i] = 0;
            }
        }
        return ;
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>>res = new ArrayList<>();
        List<Integer>temp = new ArrayList<>();
        backTrack(res,temp,new int[nums.length],nums);
        return res;
    }
}

2 组合问题-组合

LeetCode 77

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

2.1 树的确定

• 索引维护：维护一个index索引，保证当前遍历的起点

• 宽度：当前每次遍历index-n的n-index+1个数

• 高度：当前临时list长度为k，退出

2.2 代码

class Solution {
    public void backTrack(List<List<Integer>>res,List<Integer>temp,int n,int k,int index){
        if(temp.size()==k){
            res.add(new ArrayList<>(temp));
            return ;
        }
        //维护一个index，一直往后走
        for(int i = index;i<=n;i++){
            temp.add(i);
            backTrack(res,temp,n,k,i+1);
            temp.remove(temp.size()-1);
        }
    }

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

3 组合总数I

LeetCode39

3.1 树的确定

• 高度：不定，如果当前target<0直接返回，target==0，正确返回
• 宽度：candidates数组长度

3.2 代码

class Solution {
    public void backTrack(List<List<Integer>>res,List<Integer>temp,int[]candidates,int target,int index){
        //这一步必须，防止为空
        if(target<0){
            return ;
        }
        if(target==0){
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i = index;i<candidates.length;i++){

            target -= candidates[i];
            temp.add(candidates[i]);
            //可重复的精髓，下一个的起始还是当前
            backTrack(res,temp,candidates,target,i);
            target += candidates[i];
            temp.remove(temp.size()-1);

        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>res = new ArrayList<>();
        List<Integer>temp = new ArrayList<>();
        backTrack(res,temp,candidates,target,0);
        return res;
    }
}

4 组合总数

LeetCode 40

去重，需要排序后剪枝

4.1 代码

class Solution {
    public void backTrack(List<List<Integer>>res,List<Integer>temp,int[]candidates,int target,int index){
        //这一步必须，防止为空
        if(target<0){
            return ;
        }
        if(target==0){
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i = index;i<candidates.length;i++){
            //大剪枝
            if(target-candidates[i]<0){
                break;
            }
            if(i>index&&candidates[i]==candidates[i-1]){
                //小剪枝，与前一个元素相等
                continue;
            }
            target -= candidates[i];
            temp.add(candidates[i]);
            backTrack(res,temp,candidates,target,i+1);
            target += candidates[i];
            temp.remove(temp.size()-1);

        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>>res = new ArrayList<>();
        List<Integer>temp = new ArrayList<>();
        Arrays.sort(candidates);
        backTrack(res,temp,candidates,target,0);
        return res;
    }
}