【递归算法】全排列 Ⅱ

题目链接文章摘要本文解析了LeetCode上全排列II问题要求在包含重复数字的数组中返回所有不重复的全排列。通过分析决策树指出需在标准全排列解法基础上增加剪枝策略避免重复结果。详细讲解了两种剪枝思路一种是基于合法条件数字未使用且满足特定条件进入递归另一种是基于不合法条件数字已使用或与前一个重复数字冲突跳过递归。提供了对应的Java代码实现并强调了对数组排序的重要性。最后总结了两种剪枝方法的等价性为处理重复元素的全排列问题提供了清晰解决方案。一、题目解析题目给我们一个包含重复数字的数组要我们返回所有不重复的全排列。这道题目与之前的全排列那道题目相比难了一些不单单nums数组中含有重复元素连结果也要求不重复。如果我们按照全排列那题的思路去画决策树就会发现有很多重复的结果。因此在全排列那道题目的思路的基础上我们需要进行剪枝。二、算法原理 代码实现决策树根据例子 nums [ 1, 1, 1, 2 ]画出决策树部分如下这里有必要对决策树进行分析我们要想得到不重复的结果就需要有两个限制条件相同的元素只能在每一次递归时使用一次和同一个元素在一个分支只能使用一次。比如我们这里给出的例子 nums [ 1, 1, 1, 2 ]这里就有相同元素 “1”因此在每一层递归中只可以使用一个 “1”其余的都必须剪掉。上图的红色叉叉表示剪掉相同元素绿色叉叉表示该元素已被用过。接下来我们来考虑什么情况下能够进入 dfs 函数进行递归当i 0的时候可以递归吗答案是可以的我们直接将它添加到第一个位置上然后修改状态为 true 表示这个数字已被使用后续这个分支的递归中都不得再使用该数字。这时候因为所给数组中下标为 0、1 和 2 的数字都是 “1”而我们已经使用了下标为 0 的元素 “1”因此后面的元素 “1”也不得再使用了否则会出现重复结果。接下来基于第一个位置是下标为 0 的 “1”我们递归。到达第二层后判断数字状态发现下标为 0 的 “1”已被使用了那就再判断下标为 1 的 “1”它没有被使用过于是第二个位置选择下标为 1 的 “1”。这里你可能会问前面不是说过每一层递归不能使用相同元素嘛为什么这里可以呢这里的三个 “1” 虽然说是 “相同元素”但本质还是 “不同” 的我们可以给它们标上号便于区分如 1号1、2号1 和 3号1。已被使用的是 1号1但是不影响 2号1 和 3号1 的位置选择呀注意前提是 “1号1 已被使用”~选择了下标为 1 的 “1” 之后要把下标为 2 的 “1” 剪掉然后基于这个组合再递归。接下来剩下的两个元素分别对应两个结果[ 1, 1, 1, 2 ] 和 [ 1, 1, 2, 1 ]。等到回溯到第二层的时候再递归第二个位置为元素 “2” 的情况得到结果[ 1, 2, 1, 1 ]。然后继续回溯到第一层这时候由于下标为 1 和下标为 2 的元素 “1” 都被剪掉了于是不递归它们。这里满足 “当前元素 ! 前一个元素”注意这里有个前提是数组要有序因此在此之前不要忘记对 nums 进行排序噢~因此直接递归元素 2把元素 2 放到第一个位置上基于这个分支继续递归。然后判断下标为 0 的 “1”是否被用过未被使用过就把它放到第二个位置上接着发现后面两个元素 “1”于是把它们剪掉再继续递归。最后得到结果[ 2, 1, 1, 1 ]。这样不重复的全排列结果[ [ 1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 2, 1, 1 ], [ 2, 1, 1, 1 ] ]。dfs 函数函数头我们每一次递归都需要针对 nums 中的数字进行操作因此函数头的设计与全排列一样需要将 nums 作为参数。函数体本题重复的操作是根据特定条件选择数字满足了这些条件就可以继续递归不满足则跳过当然也可以考虑 “不合法” 条件来做本题。因此是要遍历 nums然后根据条件判断结果来决定是否执行后续递归和回溯的逻辑。细节问题回溯这里涉及到的回溯操作和全排列是一样的只需要在递归回来之后恢复现场即可。剪枝本题剪枝是重点根据从分析决策树得到的条件来判断从而完成剪枝。递归出口本题的递归出口与全排列一样的当 path 中的数字个数与 nums 的长度一致就更新结果并返回。代码实现思路一只考虑 “合法” 的分支class Solution { ListListInteger ret; // 记录结果 ListInteger path; // 记录单个结果 boolean[] check; // 标记数字状态 public ListListInteger permuteUnique(int[] nums) { ret new ArrayList(); path new ArrayList(); check new boolean[nums.length]; // 对 nums 排序 Arrays.sort(nums); dfs(nums); return ret; } private void dfs(int[] nums) { if (path.size() nums.length) { ret.add(new ArrayList(path)); // 更新结果 return; } for (int i 0; i nums.length; i) { // 判断何时进入递归 if ((check[i] false) (i 0 || nums[i] ! nums[i-1] || check[i-1] true)) { path.add(nums[i]); check[i] true; dfs(nums); // 回溯时恢复现场 path.remove(path.size() - 1); check[i] false; } } } }我们不妨换个思路考虑 “不合法” 即什么时候不进入 dfs 函数那就是将 “合法” 的情况反过来。合法不合法若当前数字未被使用过就递归check[i] false若当前数字被使用过就不递归check[i] true要么第一个数字可以递归要么当前数字与前一个数字不相等可以递归要么前一个数字是被使用过的可以递归i 0 或 nums[i] ! nums[i-1] 或 check[i-1] true不是第一个数字并且当前数字与前一个数字相等并且前一个数字未被使用过时不递归i ! 0 与 nums[i] nums[i-1] 与 check[i-1] false以上两个条件必须同时满足以上两个条件满足一个即可思路二只考虑 “不合法” 的分支class Solution { ListListInteger ret; // 记录结果 ListInteger path; // 记录单个结果 boolean[] check; // 标记数字状态 public ListListInteger permuteUnique(int[] nums) { ret new ArrayList(); path new ArrayList(); check new boolean[nums.length]; // 对 nums 排序 Arrays.sort(nums); dfs(nums); return ret; } private void dfs(int[] nums) { if (path.size() nums.length) { ret.add(new ArrayList(path)); // 更新结果 return; } for (int i 0; i nums.length; i) { // 判断何时不进入递归 if ((check[i] true) || (i ! 0 nums[i] nums[i-1] check[i-1] false)) continue; path.add(nums[i]); check[i] true; dfs(nums); // 回溯时恢复现场 path.remove(path.size() - 1); check[i] false; } } }文章到这里就告一段落啦若有错误请尽管指出~完