数据结构刷题（二十二）：90子集II、491递增子序列、46全排列

1.子集II

题目链接

思路：这是一道标准的组合问题+数组排序+去重。依然是使用回溯。

注意：去重代码只需要判断同一树层上是否有重复，同组合总和II（https://blog.csdn.net/xiaomingming99/article/details/129396344）

解法：

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {// 记得数组排序Arrays.sort(nums);back(nums, 0);return res;}private void back(int[] nums, int startIndex) {res.add(new ArrayList<>(path));for (int i = startIndex; i < nums.length; i++){// 去重if (i > startIndex && nums[i] == nums[i - 1])continue;path.add(nums[i]);back(nums, i + 1);path.removeLast();  // 回溯}}
}

2.递增子序列

题目链接

思路：回溯+数组去重；

回溯三部曲：

• 返回参数：startindex和数组nums。 全局变量path(记录单个结果)和res（记录结果集合）

• 终止条件：本题要求递增子序列大小至少为2，所以要判断path.size（）>=2

• 单层逻辑：for循环中，需要判断path的最后一个元素是否大于当前nums[i]，且还需要添加代码实现同一父节点下的同层上使用过的元素就不能再使用

注意：

1.&&和||同时出现时，&&优先级更高，先执行&&

2.在90.子集II (opens new window)中是通过排序原数组，判断同一树层元素是否重复来达到去重。

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

class Solution {private  LinkedList<Integer> path = new LinkedList<>();private  List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return res;}private void backtracking (int[] nums, int start) {// path的size必须大于等于2  且不需要return，因为后面可能还有更长的符合条件的序列if (path.size() >= 2) {res.add(new ArrayList<>(path));}// 标记数组  用于去重  // 比如[4,6,7,7] 使用这个数组就可以只出现一次[4,6,7] 标记6使用过int[] used = new int[201];for (int i = start; i < nums.length; i++) {// 先执行&&，判断path的最后一个元素是否大于当前值，如果是则说明不符合递增// 后执行|| 判断当前元素是否被使用过if (!path.isEmpty() && nums[i] < path.getLast()  ||(used[nums[i] + 100] == 1)) continue;used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了path.add(nums[i]);backtracking(nums, i + 1);path.removeLast();}}
}

3.全排列

题目链接

思路：回溯的排列问题。

回溯三部曲：

• 递归函数参数：参数只需要nums。不需要startIndex参数，因为排列问题，每次都要从头开始搜索。全局变量path(记录单个结果)和res（记录结果集合）

• 递归终止条件：只需要收集元素的数组path大小达到和nums数组一样大，说明到达叶子结点，可以返回

• 单层搜索的逻辑：for循环中需要判断当前元素是否已经在path中，若在直接continue。

注意： 首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，区别于组合问题。

解法：

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {back(nums);return res;}private void back(int[] nums) {// 终止条件if (path.size() == nums.length){res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++){// 判断path中是否含有遍历元素if (path.contains(nums[i]))continue;path.add(nums[i]);back(nums);path.removeLast();}}
}