网站管理办法制度/免费推广引流app

目录

一、回溯算法基础知识

二、排列问题思路及与组合的区别

2.1 回溯算法三部曲

2.2 和组合（分割、子集）等问题的区别

2.3 排列问题中的去重

三、相关算法题目

46.全排列

47.全排列 II

①数组不排序，使用set集合： 

 ②先对数组排序：

四、总结

---

一、回溯算法基础知识

详见：代码随想录刷题day46|（回溯算法篇）77.组合-CSDN博客

二、排列问题思路及与组合的区别

排列强调元素顺序，元素相同，顺序不同，是不同的排列，但 是相同的组合；

抽象成树形结构，发现要求的结果均在叶子节点中，树的深度由数组的长度来控制；

 图源自代码随想录：代码随想录 (programmercarl.com)

2.1 回溯算法三部曲

1. 回溯函数返回值和参数：返回值void，参数：原始数组，used数组；

2. 终止条件：收集到的结果，即path的长度＝数组的长度，则此时获取结果，放入结果集；

3. 单层递归逻辑：进入递归，挨个取数，i 初始化为 0，首先根据used数组判断当前元素是否取过，如果取过，跳过本次循环；否则，更改used数组中元素状态，添加元素到path中，递归进入下一层，最后回退；

2.2 和组合（分割、子集）等问题的区别

①在组合中，使用startIndex避免重复取同一个元素，在排列中，使用 used数组 标记取过的元素，之后在剩余集合中判断接下来可选取的元素有哪些；

②for循环中，排列问题 i 初始化为 0；组合中  i = startIndex；

原因：组合中，使用startIndex来去重，避免出现[1,2]和[2,1]同时存在的情况，属于重复；

但全排列中，[1,2]和[2,1]是不同的情况，都要获取，唯一需要避免的情况是：2 取过以后，就不要再重复取；

2.3 排列问题中的去重

前提：数组中存在重复元素；

抽象成树形结构可知，排列问题的去重 仍然是在非去重代码的基础上 同层去重；

①树中同层去重，先对数组进行排序，然后判断当前元素和前一个元素是否相同，同时，还要确保前一个元素没有被使用，即used数组中对应值为false才行；

为什么？

比如对于数组[1,1,2]，当在第一层递归中选择了第一个元素1，进入第二层递归中，下一层选择第二个元素1 是合法的，因为这是不同层的选择，生成的[1,1]是正确的排列，但如果只检查当前元素和前一个元素相等 然后跳过本次循环，就会失去这个正确的排列；

而需要跳过的情况是：假设此时path:[2] 那么在进入下一层递归后，i=0，首先添加第一个元素1，最终得到[2,1,1]的排列，合法，回退到[2]，此时used数组：[0,0,1] 当i = 1，添加第二个元素1 时，当前元素和前一个元素相等，且是同层，所以要跳过此次递归，而此时，used数组中，上一个元素 1 是没有被使用的状态；

当nums[i] = nums[i - 1]时，used数组中显示没有被使用，则说明是同一层，符合去重要求；

当nums[i] = nums[i - 1]时，used数组中显示已经被使用，则说明是同一子树 但 不在同一层，无需去重；

②也可以不排序，在每层中使用set集合，利用其无重复元素的特点来达到去重目的；

used数组来保证每次添加元素时 跳过list中已有的，保证同一元素只取一次；

set集合用来 在同一层中去除重复元素，前提是数组中有重复元素；

为什么是同层去重？

三、相关算法题目

46.全排列

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

47.全排列 II

①数组不排序，使用set集合： 

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {if(nums.length == 0){return result;}boolean[] used = new boolean[nums.length];backtracking(nums,used);return result;}private void backtracking(int[] nums,boolean[] used){if(path.size() == nums.length){result.add(new ArrayList<>(path));return;}Set<Integer> set = new HashSet<>(); //利用set集合来去除重复元素for(int i = 0;i < nums.length;i++){if(set.contains(nums[i])){continue;}if(used[i]) continue; //used数组来保证同一元素只取一次path.add(nums[i]);used[i] = true;set.add(nums[i]);backtracking(nums,used);path.remove(path.size() - 1);used[i] = false;}         }
}

 ②先对数组排序：

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {if(nums.length == 0){return result;}boolean[] used = new boolean[nums.length];Arrays.sort(nums);//先对数组排序backtracking(nums,used);return result;}private void backtracking(int[] nums,boolean[] used){if(path.size() == nums.length){result.add(new ArrayList<>(path));return;}for(int i = 0;i < nums.length;i++){if(used[i]) continue; //used数组来保证同一元素只取一次if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){//跳过同一层中重复的元素continue;}path.add(nums[i]);used[i] = true;backtracking(nums,used);path.remove(path.size() - 1);used[i] = false;}         }
}

四、总结

1.used数组的作用：因为排列中没有用startIndex来控制for循环中每次 遍历数组中的索引位置，每一次遍历，都是从数组的第一个元素开始取，那么这种情况下，要保证 选取的元素 不是path集合中已经存储的，就要用used数组来控制；

2.和组合的区别；

3.易忘：最后回退的时候，used数组中的状态也要改为false；

4.先对数组排序再去重的条件判断 要理解，容易出错；