DAY29| 491.递增子序列 ,46.全排列 ,47.全排列II

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

文章目录

- 491.递增子序列
- 46.全排列
- 47.全排列II

491.递增子序列

文字讲解：递增子序列

视频讲解：递增子序列

**状态：这题看了文字讲解才AC，掌握了如何在回溯里通过Set集合来对同层节点去重

思路：

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}//本题的关键在于，同层不能有重复元素，当前层的节点不能大于上一层的值public void backTracking(int[] nums, int startIndex) {if (startIndex>=nums.length) {return;}//借助set集合去重HashSet hs = new HashSet();for (int i = startIndex; i < nums.length; i++) {if ((!tempList.isEmpty() && tempList.get(tempList.size()-1) > nums[i]) || hs.contains(nums[i])) {continue;}hs.add(nums[i]);tempList.offer(nums[i]);if (tempList.size()>1) {result.add(new ArrayList<>(tempList));}backTracking(nums, i+1);tempList.pollLast();}}
}

46.全排列

文字讲解：全排列

视频讲解：全排列

状态：做完组合类的题，这题好简单

思路：

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();boolean[] usedArr;public List<List<Integer>> permute(int[] nums) {this.usedArr = new boolean[nums.length];for (int i = 0; i < this.usedArr.length; i++) {this.usedArr[i] = false;}backTracking(nums);return result;}public void backTracking(int[] nums) {if (tempList.size()==nums.length) {//收集result.add(new ArrayList<>(tempList));return;}for (int i = 0; i < nums.length; i++) {if (usedArr[i]) {continue;}usedArr[i]=true;tempList.offer(nums[i]);backTracking(nums);tempList.pollLast();usedArr[i]=false;}}
}

47.全排列II

文字讲解：全排列II

视频讲解：全排列

状态：将前两题的思路整合，这题ok

思路：

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);this.used = new boolean[nums.length];for (int i = 0; i < used.length; i++) {used[i] = false;}backTracking(nums);return result;}public void backTracking(int[] nums) {if (tempList.size()==nums.length) {result.add(new ArrayList<>(tempList));return;}HashSet<Integer> hs = new HashSet();for (int i = 0; i < nums.length; i++) {if (used[i] || hs.contains(nums[i])) {continue;}hs.add(nums[i]);used[i] = true;tempList.offer(nums[i]);backTracking(nums);tempList.pollLast();used[i] = false;}}
}