【LeetCode刷题日记】47.全排列Ⅱ

个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺大家好我是代码不加冰今天刚刚考完六级啥单词都不记得了全靠蒙了保佑我能及格吧今天到了我们的每日刷题环节。题目背景给定一个可包含重复数字的序列nums按任意顺序返回所有不重复的全排列。示例 1输入nums [1,1,2]输出[[1,1,2], [1,2,1], [2,1,1]]示例 2输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示1 nums.length 8-10 nums[i] 10题目分析这道题的题目很简洁是我们前面做过的全排列的变式也是利用回溯算法来解决的具体的差异让我们看看吧。可以用一句话概括46 题的输入数字“独一无二”而 47 题的输入数字“有重复”但两道题都要求最终的排列结果不能重复。题目区别为了更直观地理解我们可以从以下三个维度来看它们的区别1. 输入与输出的对比假设两道题的输入数组长度都为 3维度第 46 题全排列 (Permutations)第 47 题全排列 II (Permutations II)输入数组nums [1, 2, 3]无重复数字nums [1, 1, 2]有重复数字排列总数$3! 6$ 种结果只有 3 种结果去重后最终答案[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]][[1,1,2], [1,2,1], [2,1,1]]2. 决策树搜索空间的区别第 46 题因为每个数字都不同只要保证在同一条路径上不重复使用同一个位置的数字即可代码里用一个简单的used数组或contains()就能搞定。第 47 题因为有重复数字比如两个1如果像 46 题那样直接去搜就会出现两条一模一样的路径比如“第一个 1 配合 2”和“第二个 1 配合 2”。这就需要剪枝把重复的分支在萌芽状态就砍掉。3.代码实现上的区别两道题都使用回溯法但第 47 题多了两处关键改动// 区别 147 题必须先排序 Arrays.sort(nums);为什么要排序只有让相同的数字挨在一起比如[1, 1, 2]我们才能在遍历到第二个1时轻易地通过nums[i] nums[i-1]发现它和前一个数字重复了。// 区别 247 题多了核心剪枝条件 if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; }这行代码在干嘛当我们准备选择当前的nums[i]时如果发现它和前一个数字nums[i-1]一样并且!used[i-1]意味着前一个1在当前层已经被用过并撤销了那就说明以这个数字开头的排列我们刚才已经完全穷举过了。为了避免创造出重复的兄弟分支直接continue跳过。核心去重代码关键的剪枝代码就是这一行if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; }注意这里的!used[i - 1]它是实现树层去重的灵魂。为什么used[i - 1]是去树层当满足nums[i] nums[i - 1]时有两种情况情况 Aused[i - 1] true树枝上重复不剪枝这意味着nums[i - 1]前一个 1已经被选过了并且现在正处于递归的更深层也就是在同一条树枝上。合法性这是合法的因为我们要凑出[1, 1, 2]这样的排列第一个1和第二个1同时出现在一条路径里是完全没问题的。所以这时候!used[i - 1]为false不会触发continue程序继续向下搜索。情况 Bused[i - 1] false树层上重复必须剪枝这意味着nums[i - 1]前一个 1现在是空闲的。为什么它是空闲的因为它刚刚被使用完并且在回溯的过程中被撤销了选择used[i - 1]被重新置为了false。场景还原在决策树的第一层我们先选了第一个1nums[0]一路向下递归拿到了所有以第一个1开头的排列比如[1, 1, 2],[1, 2, 1]。接着我们回溯把第一个1释放掉此时used[0]变回false。循环继续i移到了第二个1nums[1]。此时nums[1] nums[0]成立且used[0] false。这就触发了剪枝。因为如果允许选择第二个1开头那么后续必定会复制出一套一模一样的[1, 1, 2]分支。我们来看看这个过程的直观对比一句话总结 如果used[i - 1] false说明左边那个和自己一样的数字已经把属于它的所有排列情况都穷举完了。此时轮到你你如果再上场只会把人家走过的老路再走一遍产生一堆一模一样的双胞胎答案所以必须在这里把它拦截剪枝。举例分析例子nums [1, 1, 2]排序后还是[1, 1, 2]javaif (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;!used[i - 1]表示前一个相同元素在树层的同一层中没有被使用也就是刚被回溯撤销过。此时如果选了当前元素就会产生和之前选前一个元素时完全相同的排列 →跳过初始状态textnums [1a, 1b, 2] (a和b值相同用来区分位置) used [false, false, false]第一层选第一个数i 0 (1a)used[0] false且前一个不存在 → 选择 1a状态path [1a],used [T, F, F]→ 进入下一层i 1 (1b)当 i0 回溯回来后used[1]falsenums[1]nums[0]且!used[0]true因为 1a 在这一层并没有被使用它已经被撤销了→被跳过✅ 这是去重的关键避免同一层选 1b 产生[1b,...]和[1a,...]重复i 2 (2)used[2]false且与前一个 1b 不同 → 选择 2状态path [2],used [F, F, T]→ 进入下一层第二层路径 [1a] 时的下一层当前path [1a],used [T, F, F]i 0→used[0]true跳过i 1 (1b)→used[1]false, 前一个是 1a值相同但 nums[1]!nums[0]值是相同的但 i0 nums[1]nums[0] !used[0]falseused[0] 是 true→ 不跳过因为 !used[0] 为 false所以这里允许选择 1b✅ 选择 1bpath[1a,1b],used[T,T,F]→ 下一层i 2 (2)→ 后面会选到[1a,2]第三层路径 [1a,1b]path[1a,1b],used[T,T,F]只剩 i2 (2) 可选 →path[1a,1b,2]→ 收集结果[1,1,2]回溯后到[1a]继续 i2 选 2 →[1a,2]再选 1b →[1a,2,1b]→ 结果[1,2,1]回到第一层处理 i2 (2)当[1a]和[1b被跳过]都处理完后回到第一层 i2初始第一层不是子层used [F,F,F]但之前第一层选过 1a现在要选 2选 2 →path[2],used[F,F,T]→ 下一层在子层里1a 和 1b 都可以选不会重复因为值相同但 used 条件不同产生[2,1a,1b]→ 结果[2,1,1]关于撤销的逻辑还是有很多新手搞不明白的只要记住上面时候是递归的结束就可以了因为递归结束return 之后会返回到上一层递归函数中执行上一层递归函数中backtrack()调用后面的代码即撤销代码。还有一个树枝重复元素的处理有两种写法可以直接if (used[i] false) { used[i] true;//标记同⼀树⽀nums[i]使⽤过防止同一树枝重复使用 path.add(nums[i]); backTrack(nums, used); path.remove(path.size() - 1);//回溯说明同⼀树层nums[i]使⽤过防止下一树层重复 used[i] false;//回溯 }也可以先判断// 如果当前数字已经被使用过直接跳过 if (used[i]) { continue; }题目答案import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public ListListInteger permuteUnique(int[] nums) { ListListInteger res new ArrayList(); if (nums null || nums.length 0) { return res; } // 1. 必须先排序这是去重的前提 Arrays.sort(nums); // 记录数字是否被使用过 boolean[] used new boolean[nums.length]; // 2. 开始回溯 backtrack(nums, used, new ArrayList(), res); return res; } private void backtrack(int[] nums, boolean[] used, ListInteger track, ListListInteger res) { // 触发结束条件走完了一条完整的路径 if (track.size() nums.length) { res.add(new ArrayList(track)); return; } for (int i 0; i nums.length; i) { // 如果当前数字已经被使用过直接跳过 if (used[i]) { continue; } // 核心剪枝条件去重 // nums[i] nums[i - 1] 说明当前数字和上一个数字相同 // !used[i - 1] 说明上一个相同的数字在当前层已经被撤销/使用过了 if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; } // 做选择 track.add(nums[i]); used[i] true; // 进入下一层决策树 backtrack(nums, used, track, res); // 撤销选择回溯 used[i] false; track.remove(track.size() - 1); } } }