labuladong算法——回溯框架

解决一个回溯问题，实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就在于for循环中的backtrack递归，在递归之前做出选择，在递归之后撤销选择。

---

一、全排列问题 LC46

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

 然后找到框架去重新审视：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        将选择从选择列表中移除
        路径.add(选择)
        backtrack(路径, 选择列表)
        路径.remove(选择)
        将选择加入选择列表

import java.util.LinkedList;
 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
 
    //外围放一个双重list保存结果
    List> res = new LinkedList<>();
 
    public List> permute(int[] nums) {
        //这个track存放的是res里面的某个list,比如[1,2,3],
        //当然也有[1,2]的时候,就是不断往里加.
        LinkedList track = new LinkedList<>();
        //这个boolean的used主要是标记用了没用
        //比如123 如果是0就标记1已经用过了,然后把1拿出来放到track里
        boolean[] used = new boolean[nums.length];
        //传入递归的东西:原始数组 正在递归的track 是否用过的used
        trackback(nums, track, used);//不需要返回值
        return res;
    }
    void trackback(int[] nums,LinkedList track,boolean[] used){
        //当nums中所有的数字都被用完的时候,返回
        if(track.size()==nums.length){
            res.add(new LinkedList(track));
            return;
        }
        //遍历nums中的每个数字
        //注意 每次迭代都要遍历 但是如果遍历过的就直接过
        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            //给track加上最后一位
            track.add(nums[i]);
            //标记已经用过了
            used[i] = true;
            trackback(nums,track,used);
            track.removeLast();
            used[i] = false;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

---

二、子集（元素无重不可复选）LC78

题目给你输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集。

 这道题一个显而易见的问题在于 1 2 3 和 2 1 3是相同的。

这里我们采用一个start来标记当前遍历到哪个位置了——比如1 这个时候start就是 1 代表0位置的1已经被遍历了，接下来只需要考虑2和3就行了。

这个start应该在递归里面传递下去，每次创建新的track都需要start

List> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList track = new LinkedList<>();
 
// 主函数
public List> subsets(int[] nums) {
    backtrack(nums, 0);
    return res;
}
 
// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(int[] nums, int start) {
 
    // 前序位置，每个节点的值都是一个子集
    res.add(new LinkedList<>(track));
    
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

---

三、组合（元素无重不可复选）

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

import java.util.LinkedList;
 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List> res = new LinkedList<>();
    LinkedList track = new LinkedList<>();
    public List> combine(int n, int k) {
        back(1, n, k);
        return res;
    }
    void back(int start,int n,int k){
        if(track.size()==k){
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i <= n; i++) {
            track.add(i);
            back(i+1, n, k);
            track.removeLast();
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

容易迷惑的点有两个，一个是n是从1开始的，这样才能保证track=k的时候，track里面有k个元素。

另外一个是用start标志的，因为这里面不是元素，是顺序的数组，实际上不用start也可以用一个nums数组来标记，不过start明显更方便。

---

四、子集/组合（元素可重不可复选）

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集。

比如输入 nums = [1,2,2]，你应该输出：

[ [],[1],[2],[1,2],[2,2],[1,2,2] ]

 

这个的问题也很简单：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：

import java.util.Arrays;
 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList track = new LinkedList<>();
 
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);//先排个序
        backtrack(nums, 0);
        return res;
    }
 
    void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(track));
 
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 做选择
            if (i > start && nums[i] == nums[i - 1]) continue;
            //剪枝逻辑 如果等于就跳过 注意这里是从0开始的所以必须判断一下
            track.addLast(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            backtrack(nums, i + 1);
            // 撤销选择
            track.removeLast();
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

---

五、排列（元素可重不可复选）

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

 最关键的就是脑子清醒一点，知道在递归过程中哪步是干什么的。

这里我们用一个prenum保存上一个枝的数字——千万注意，这个枝是在迭代之前就要保存好的，比如1 1 3 在回溯到第二个1之后，要判断和上个1是否相同，如果相同就直接跳过。

import java.util.LinkedList;
 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List> res = new LinkedList<>();
    LinkedList track =new LinkedList<>();
    boolean[] used;
    public List> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        back(nums);
        return res;
    }
    void back(int[] nums){
        int prenum = -100;
        if(track.size()==nums.length){
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]||prenum==nums[i]){
                continue;
            }
            //这里就是最关键的剪枝逻辑 prenum在进入迭代之前就要保存好
            //迭代完成,完成i=1这个下面的树迭代之后,i=2的时候,才开始比对prenum和i=2的时候的1
            //也就是说 比较的其实是i=1时候的枝和i=2时候的枝
            track.add(nums[i]);
            prenum = nums[i];
            used[i] = true;
            back(nums);
            track.removeLast();
            used[i] = false;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)