491.递增子序列
题目链接：力扣
思路
这道题目不能排序， 因为要保证目前原数组中的递归的子数组
数组中存在重复的元素，所以需要对树层进行去重
因为不能排序，所以无法使用used数组进行去重
要做到能收集数组中的所有的情况，要做到两点:
1、当一条树枝中后面的元素不满足递增的情况，需要跳过，继续收集后面的元素
2、当树层中出现中已经使用过的数字时，要跳过，继续收集后面的元素，因为不能排序，所以需要使用set集合记录这层树层中出现过的元素
这个set集合不用跟着回溯，因为就是记录这层的元素出现情况
每进一层递归都会创建一个新的set集合
需要注意的一点是收集结果的条件：
形成递增至少需要两个元素，所以需要 path.size() > 1
递增子序列
class Solution { LinkedList<Integer> path = new LinkedList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { backtracking(nums,0); return result; } void backtracking(int[] nums, int startIndex) { if (path.size() > 1) { result.add(new ArrayList<>(path)); } HashSet<Integer> set = new HashSet<>(); for (int i = startIndex; i < nums.length; i++) { // 不满足递增的情况 if (!path.isEmpty() && nums[i] < path.getLast()) { continue; } // 使用过了的数字 if (set.contains(nums[i])) { continue; } set.add(nums[i]); path.add(nums[i]); backtracking(nums,i+1); path.removeLast(); } } }
46.全排列
题目链接：力扣
思路
这道题目中没有重复的元素，所以不用考虑去重的问题，因为是排列问题，所以递归中的每一次循环都需要从第一个元素进行处理，但是这样就会出现添加同一元素的问题，所以需要对这样情况进行处理
在下面排列的数结构图进行分析
再有一种思路就是使用used数组进行树枝去重，使用used数组标记哪个元素已经使用过了
全排列
通过path排除
class Solution { LinkedList<Integer> path = new LinkedList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { backtracking(nums); return result; } void backtracking( int[] nums) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); } for (int i = 0; i < nums.length; i++) { if (path.contains(nums[i])) { continue; } else { path.add(nums[i]); backtracking(nums); path.removeLast(); } } } }
通过used[]数组排除
class Solution { LinkedList<Integer> path = new LinkedList<>(); List<List<Integer>> result = new ArrayList<>(); boolean[] used; public List<List<Integer>> permute(int[] nums) { used = new boolean[nums.length]; backtracking(nums); return result; } 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] == true) { continue; } path.add(nums[i]); used[i] = true; backtracking(nums); used[i] = false; path.removeLast(); } } }
47.全排列 II
题目链接：力扣
思路
因为集合中有重复的元素，不仅要对树层进行去重，也要对树枝进行去重，最好的选择就是使用used数组，所以这道题目关键就是在去重
path只适合对树枝进行去重，因为path只作用于一条树枝
nums[i] == nums[i-1] && used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
nums[i] == nums[i-1] && used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
全排列||
class Solution { LinkedList<Integer> path = new LinkedList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); boolean[] used = new boolean[nums.length]; Arrays.fill(used,false); backstarking(nums,used); return result; } void backstarking(int[] nums,boolean[] used){ if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过 // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过 // 如果同⼀树层nums[i - 1]使⽤过则直接跳过 // used数组避免同树枝上的相同元素被去重 if (i > 0 && nums[i] == nums[i-1] && used[i - 1] == false) { continue; } //如果同⼀树⽀nums[i]没使⽤过开始处理 //如果对应的used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过 if (used[i] == false) { path.add(nums[i]); used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用 backstarking(nums,used); path.removeLast();//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复 used[i] = false; } } } }
