代码随想录算法训练营第二十九天| LeetCode491.递增子序列* 、LeetCode46.全排列*、LeetCode47.全排列 II

#LeetCode 491. Non-decreasing Subsequences

#LeetCode 491. 视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

首先，本题不能考虑首先对数组排序，排序会导致数组直接变为一个递增的序列。本题依然是一个组合问题，所以无序，i 在for loop中依然是从startIndex 开始。与之前的去重逻辑不同，每一层会有一个uset 变量，是记录本层元素是否重复使用，新的一层uset都会重新定义，不是之前去重那样的全局变量，同样回溯的时候也不需要删除元素，也是在树层去重。

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = 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;}if (path.size() > 1) {result.add(new ArrayList<>(path));}HashSet<Integer> uset = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {if (!path.isEmpty() && path.getLast() > nums[i] || uset.contains(nums[i])) {continue;}uset.add(nums[i]);path.addLast(nums[i]);backtracking(nums, i + 1);path.removeLast();}}
}

#LeetCode 46. Permutations

#LeetCode 46. 视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

与之前的组合问题不同的地方在于，排列是有序的，[1, 2] 和[2, 1] 是不同的，如果用used 数组，那么在for loop 遍历的时候也是通过used 数组的标记，来判断下一次取具体哪一个数字。

回溯方法代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new LinkedList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}used[i] = true;path.addLast(nums[i]);backtracking(nums, used);used[i] = false;path.removeLast();}}
}

#LeetCode 47. Permutations II

#LeetCode 47. 视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

如果完成了之前的题目，那么这个题目较简单，排列的思想与上一个题目相似，去重与之前组合去重相似，记得数组需要排序。

回溯方法代码：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backtracking(nums, used);return result;}public void backtracking(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new LinkedList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {continue;}if (used[i]) {continue;}path.addLast(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.removeLast();}}
}