代码随想录算法训练营第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而不是breakuset[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而不是breakuset.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;    // 取过的数标记为1used[i] = true;path.add(nums[i]);backTracking(nums, used);used[i] = false;path.removeLast();}}
}