代码随想录刷题day25丨491.递增子序列，46.全排列，47.全排列 II

本文主要是介绍代码随想录刷题day25丨491.递增子序列，46.全排列，47.全排列 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录刷题day25丨491.递增子序列，46.全排列，47.全排列 II

1.题目

1.1递增子序列

题目链接：491. 非递减子序列 - 力扣（LeetCode）
视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
解题思路：回溯
- 用[4, 7, 6, 7]这个数组来举例，抽象为树形结构如图：

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums, 0);return result;}void backtracking(int[] nums, int startIndex) {if(path.size() >= 2){result.add(new ArrayList<>(path));}Set<Integer> tempSet = new HashSet<>();// 使用set对本层元素进行去重for (int i = startIndex; i < nums.length; i++) {if((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || tempSet.contains(nums[i])){continue;}tempSet.add(nums[i]);path.add(nums[i]);backtracking(nums,i + 1);path.remove(path.size() - 1);}}
}

总结：
- 本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！
- 数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组。

1.2全排列

题目链接：46. 全排列 - 力扣（LeetCode）
视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

解题思路：回溯

以[1,2,3]为例，抽象成树形结构如下：

回溯三部曲

递归函数参数

List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
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(used[i] == true){continue;}path.add(nums[i]);used[i] = true;backtracking(nums,used);used[i] = false;path.remove(path.size() - 1);
}

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];backtracking(nums,used);return result;}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(used[i] == true){continue;}path.add(nums[i]);used[i] = true;backtracking(nums,used);used[i] = false;path.remove(path.size() - 1);}}
}

总结：
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素了

1.3全排列 II

题目链接：47. 全排列 II - 力扣（LeetCode）
视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
解题思路：回溯
- 去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
- 以示例中的 [1,1,2]为例（为了方便举例，已经排序）抽象为一棵树，去重过程如图：
- 图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.sort(nums);backtracking(nums, used);return result;}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] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == true) {continue;}path.add(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.remove(path.size() - 1);}}
}