#Java #全排列 #回溯

开源学习资料

Feeling and experiences：

递增子序列：力扣题目链接

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

这道题要注意的点：

目的就是早递增子序列，所以不能对原来的数值进行排列

所以不能像子集II 那个问题一样，先给数组中的元素排好顺序，再来用used数组标记。

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {back(nums,0);return ans;}public void back(int []nums,int startIndex){//什么时候收集？if(path.size() >= 2){ans.add(new ArrayList<>(path));}//该题又要去重，又要使其为递增//建立一个Set集合Set<Integer> set = new HashSet<>();for(int i=startIndex;i<nums.length;i++){if(!path.isEmpty() && path.get(path.size()-1)>nums[i] || set.contains(nums[i])){continue;}set.add(nums[i]);path.add(nums[i]);back(nums,i+1);path.remove(path.size()-1);}}
}

 Set集合的使用：（为什么Set集合放在for循环外部？）

1. 去重的目的：

目的是确保在同一递归层级中，不会因为重复选择同一个元素而生成重复的子序列。这是为了防止例如 [1, 2, 2] 这样的数组生成两个相同的子序列 [1, 2]。

2. 作用域的问题：

如果 Set 被放在 for 循环内，那么每次循环时都会创建一个新的 Set。这意味着对于每个元素，Set 都是空的，所以每个元素都会被认为是“新”的，从而无法阻止同一层级中的重复选择。

3. 保持状态：

将 Set 放在 for 循环外部，可以让它在整个递归调用的特定层级中保持状态。这样，当递归到同一层级的不同部分时，Set 中已经包含了该层级中先前考虑过的元素，有效防止重复。

全排列：力扣题目链接

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

经典的模板题

这里引用代码随想录中的图解：

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean []used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];Arrays.fill(used,false);back(nums);return ans;}public void back(int []nums){if(path.size() == nums.length){ans.add(new ArrayList<>(path));}for(int i = 0;i<nums.length;i++){//判断是否用过if(used[i] == true){continue;}used[i] = true;path.add(nums[i]);back(nums);used[i] = false;path.remove(path.size()-1);}}
}

充分利用了used数组~

全排列 II：力扣题目链接

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

关键点：树层去重

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean []used;public List<List<Integer>> permuteUnique(int[] nums) {//把数组进行排列Arrays.sort(nums);used = new boolean[nums.length];Arrays.fill(used,false);back(nums);return ans;}public void back(int []nums){if(path.size() == nums.length){ans.add(new ArrayList<>(path));return;}for(int i =0;i<nums.length;i++){//去重if(i>0 && nums[i] == nums[i-1] && used[i-1] == true){continue;}if(used[i] == false){used[i] = true;path.add(nums[i]);//回溯back(nums);path.remove(path.size()-1);used[i] = false;}}}
}

 整体思路：

• 首先，将数组排序。这样，相同的元素会相邻，便于去重。
• 在 back 方法中，使用 if 条件进行去重：
• if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true)：这个条件检查当前元素是否与前一个元素相同，并且前一个元素已经被使用过。如果是，就跳过当前元素，避免在同一树层生成重复的排列。

 

此时相望不相闻，

愿逐月华流照君~

Fighting!