代码随想录算法训练营第29天（回溯算法05 | * 491.递增子序列 * 46.全排列 * 47.全排列 II

491.递增子序列

本题和大家刚做过的90.子集II非常像，但又很不一样，很容易掉坑里。
题目链接： 491.递增子序列
文章讲解： 491.递增子序列
视频讲解： 491.递增子序列

解题思路

在90.子集II中我们是通过排序，再加一个标记数组来达到去重的目的。

而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

与90.子集II不同的点

1. 不能排序
2. 不能用之前的used[]数组，而要用set，且set不需要跟着回溯，只负责本层里面取了哪些元素
3. 需要判断每个path中元素个数是否大于等于2
4. 需要判断每个path是否是递增的

回溯三部曲

1. 递归函数参数：

• 全局变量result和path
• startIndex

2. 终止条件：
   要遍历整个树，可以没有
3. 单层遍历逻辑

• 去重逻辑
• 局部变量HashSet uset; 记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！
  

// uset用数组实现 效率高一些
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    public void backTracking(int[] nums, int startIndex){
        if(path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        if(startIndex >= nums.length){ // 这个终止条件可以没有，因为我们要遍历整个树
            return;
        }
        int[] uset = new int[201];
        for(int i = startIndex; i <nums.length; i++){
            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i] || uset[nums[i] + 100] == 1) continue; //注意是continue而不是break
            uset[nums[i] + 100] = 1;
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }    
}

// // uset用set实现
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    public void backTracking(int[] nums, int startIndex){
        if(path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        if(startIndex >= nums.length){ // 这个终止条件可以没有，因为我们要遍历整个树
            return;
        }
        HashSet<Integer> uset = new HashSet<>();
        for(int i = startIndex; i <nums.length; i++){
            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i] || uset.contains(nums[i])) continue; //注意是continue而不是break
            uset.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46.全排列

本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
题目链接： 46.全排列
文章讲解： 46.全排列
视频讲解： 46.全排列

解题思路

不需要i = startIndex控制for循环开始位置，每次从i = 0开始
需要判断当前元素是否已经取过

遇到的难点

如何不重复取自身元素：used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次

思考

这道题的used数组和之前题目中的used数组作用的不同

• 这道题的used数组：记录此时path里都有哪些元素使用了
• 之前题目中的used数组：树层上对组合去重，一般要先将数组排序
  

// 解法1：通过判断path中是否存在数字，排除已经选择的数字
// 感觉这种比解法2好理解
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) return result;
        backtrack(nums, path);
        return result;
    }
    public void backtrack(int[] nums, LinkedList<Integer> path) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
        }
        for (int i =0; i < nums.length; i++) {
            // 如果path中已有，则跳过
            if (path.contains(nums[i])) {
                continue;
            } 
            path.add(nums[i]);
            backtrack(nums, path);
            path.removeLast();
        }
    }
}

// 法2：通过used判断是否path中已取过当前数字
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return result;
    }
    public void backTracking(int[] nums){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
        }
        for(int i = 0; i < nums.length; i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums);
            used[i] = false;
            path.removeLast();

        }
    }
}

47.全排列 II

本题 就是我们讲过的40.组合总和II去重逻辑 和46.全排列的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行
题目链接： 47.全排列 II
文章讲解： 47.全排列 II
视频讲解： 47.全排列 II

解题思路

40.组合总和II去重逻辑 和46.全排列的结合

注意点

nums数组排序

Arrays.sort(nums);

树层去重

if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;  // 树层去重

取过的元素不再重复取

if(used[i] == true) continue;    // 取过的数标记为1

拓展

去重代码中，如果改成 used[i - 1] == true， 也是正确的!
这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
树枝去重图例

需要加深理解的点（需复习

• 树层去重和树枝去重
• used数组在不同题中的作用
• 为什么这道题的used数组需要作为参数参与递归结合40.组合总和II和90.子集II进行思考
• 491.递增子序列中的uset
  

小总结

491.递增子序列 不能用之前的used[]数组，而要用set，且set不需要跟着回溯，只负责本层里面取了哪些元素 used数组不需要回溯，不需要放在递归参数里面
46.全排列 used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次 used数组要回溯，要放在递归参数里面
47.全排列 II used数组：去重＋取过的元素不再重复取 used数组要回溯，要放在递归参数里面

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums, used);
        return result;
    }
    public void backTracking(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i =0; i < nums.length; i++) {
            // 树层去重
            if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) continue;  // 树层去重
            if(used[i] == true) continue;    // 取过的数标记为1
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums, used);
            used[i] = false;
            path.removeLast();
        }
    }
}