回溯---全排列(II) Posted on 2021-07-29 00:00:00 2021-07-29 00:00:00 by Author 摘要 给定一个数组 nums(数组中得元素可能有重复元素，有可能没有重复元素) ，你能得到该集合的所有可能的全排列吗？？？ # 回溯---全排列(II) 1. 题目描述 - 给定一个可包含重复数字的序列 `nums` ，**按任意顺序** 返回所有不重复的全排列。 - **提示：** - `1 <= nums.length <= 8` - `-10 <= nums[i] <= 10` 2. 示例描述 - 示例一 ``` 输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]] ``` - 示例二 ``` 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` 3. 解题思路 - 首先拿到题目时，可以分析这道题与全排列(I)的不同之处在于，本题中的集合中有相同的元素，而全排列(I)中集合中的元素各不相同，这就使得有相同元素的集合进行全排列的时候，排列集合中会出现重复的子集合。 - 那么在进行回溯与遍历的过程中怎么达到去重的效果尼？首先拿示例一来说明，对于集合[1,1,2]，进行全排列的时候，一般做法是这样的：首先从[1,1,2]随机选取一个数，可以选择1(下标为0)，选择1(下标为1)，选择2，第一层有三种选择的可能，假如第一层选择 1(下标为0 的元素)，到达第二层时的集合为[1,2],从这个集合随机选择一个数，可以选择1，可以选择2，有两种可能，这里可以选择1，此时到达第三层的时候能够遍历的集合为[2]，这一层只能选择[2],此时该次递归遍历的子集和为[1,1,2]。此时第三层遍历完成，需要回溯到第二层，由于第二层的第一次选择了元素1，这次就只能选择元素2了，再次来到第三层，此时能够遍历的集合为[1]，这一层选择元素1,此时递归遍历子集合为[1,2,1]。此时返回到第二层，第二层集合也遍历完成了，在返回到第一层。由于第一层第一次我们选择了元素1，那么这一层如果还选择元素1(下标为1)的 话,之后的排列就会和前面的子集重复了。 - 所以要达到去重的效果，那么我们在每次进行元素向下层递归时，可以选择这样做，首先我们判断要选取的元素在本层中是否出现过，如果在遍历该元素时，之前已经有相同的元素进行排列了，那么该元素就不用再次参加排列了，那么怎么判断尼，我们可以对集合进行排序，相同的元素肯定排列在一起，如果该元素之前的一个位置的元素与当前元素相等，并且该元素之前已经遍历过了，那么本层遍历的该元素 就不用参加排列了，从而达到去的得效果。 - 以上具体逻辑以及思想见如下代码。 4. 代码示例 ```java //最终结果集 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { //集合中有重复元素，首先对集合元素排序，方便后续的去重操作 Arrays.sort(nums); //用来记录遍历时，是否该元素已经加入集合中 boolean[] used = new boolean[nums.length]; for (int i = 0; i < used.length; i++) { used[i] = false; } //调用自己写的递归回溯算法 trackBacking(nums, new ArrayList<>(), used); return result; } public void trackBacking(int[] nums, List<Integer> tempResult, boolean[] used) { //如果集合中的元素个数与数组长度相等，那么说明该次组合已经完成 //把该次的结果加入 最终结果集合中 if (tempResult.size() == nums.length) { result.add(new ArrayList<>(tempResult)); return; } //否则继续进行遍历集合中其他元素 for (int i = 0; i < nums.length; i++) { //这一步是重点 //首先i>0，防止数组下标越界 //如果本层本次遍历的元素与前一个元素相等(数组已经排序了)，并且上一个元素已经使用过了 //那么说明本元素不用再次继续参加组合排列了，因为之前有元素已经进行组合排列了，从而达到去重的效果 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue; //当前元素在本层时未使用，说明该元素可以参加组合排列 if (used[i] == false) { //当前元素加入结果集中 tempResult.add(nums[i]); //当前元素已经使用了 used[i] = true; //继续下层递归 trackBacking(nums, tempResult, used); //回溯到本层开始的状态 tempResult.remove(tempResult.size() - 1); //同时used数组回溯本层初始状态，用来判断该层集合的元素在之前是否已经进行排列组合了 used[i] = false; } } } ```
{{ item.content }}
{{ child.content }}