全排列 II

笨办法：照全排列排出全部 n! 条，再丢进 set 去掉重复。可重复越多，白排的越多，纯属浪费。我们要在生成时就不排重复的。

先把数组排序，让相同的数挨在一起。回溯时仍是「选择→递归→撤销」，只多一刀剪枝：在同一层，如果这个数和左边那个一样、而左边那个还没被选，就跳过它。

排序前 · 原始输入：原始输入是 [2, 1, 1]。注意：两个 1 现在被 2 隔在了两头。这样剪枝那刀「看左边一个是不是同值」就判不出来——所以第一步必须先排序。

排序后 · 两个 1 挨到一起：执行 nums.sort()：[2,1,1] 变成 [1, 1, 2]，下标 0 和下标 1 这两个 1 现在紧挨着了。看，2 挪到了最右边——这就是排序真正干的活。

排序后开始：现在从排好序的 [1, 1, 2] 开始回溯。path 空，三个数都没用过，res 空。

第1层 · 选下标0的 1：第一层先选下标 0 的 1：标记已用，放进 path。path = [1]。

第2层 · 选下标1的 1：第二层来到下标 1 的 1。它和左边一样，但左边那个 used[0] 是 True（在用），不跳过。选它，path = [1, 1]。

第3层 · 选 2 · 收集：第三层只剩 2，凑满 [1, 1, 2]，记下第一条 [1,1,2]。然后开始回溯。

撤回到 [1]：撤销 2、再撤销下标1的 1，退回 path = [1]。第二层换 2 试试。

第2层 · 改选 2：第二层选 2。path = [1, 2]。第三层只剩下标1的 1 了。

第3层 · 选 1 · 收集：第三层选下标1的 1，凑满 [1, 2, 1]，记下第二条 [1,2,1]。以下标0的 1 开头的排列全找完了。

一路撤销回开头：继续撤销，退回 path 空。现在第一层准备换下一个数——轮到下标 1 的 1 了。注意看下面这一帧。

灵魂帧 · 同层跳重复：第一层轮到下标 1 的 1。它和下标 0 的 1 相同，而下标 0 的 used 是 False（刚撤销、本层没在用）——这正是要跳过的情形。它打头能排出的 [1,1,2]、[1,2,1] 刚才下标0的 1 已经排过了，再排就重复。直接跳过。

第1层 · 选 2：跳过那个 1，第一层选 2。path = [2]。剩下两个 1。

第2层 · 选下标0的 1：第二层选下标 0 的 1。path = [2, 1]。

第3层 · 选 1 · 收集：第三层选下标1的 1（它的 used[0]=True，不跳），凑满 [2, 1, 1]，记下第三条 [2,1,1]。

再跳一次重复：撤回 path = [2]，第二层想换下标 1 的 1。可它和下标 0 的 1 相同、且 used[0]=False，又跳过。这条分支到头了。

全部找齐：[1,1,2] · [1,2,1] · [2,1,1] 三条，不重不漏。没有那刀剪枝，会多出一份重复的 [1,1,2] 和 [1,2,1]。

去重的关键不在结果端，而在生成端：同一层里，相同的数只让最左边那个去打头。

雷区实演① · 把条件写反：把 not 漏掉、写成「used[i-1] 为 True 才跳」会怎样？跟着跑一遍。第一层下标 0 的 1：i=0 没左邻，照常选，path = [1]。

雷区实演② · 这次反而把第2层的 1 叉了：第二层轮到下标 1 的 1，此刻 used[0]=True。写反的条件「used[i-1] 为 True 才跳」在这里触发了——把它叉掉。注意：正确的 not 版本，这一步是要选的；两版正好跳的时机相反。

雷区实演③ · 答案没错，但白跑了一堆：绕来绕去，写反版最后居然也凑出了对的 3 条——结果不错！但它一路上多撞了好几次死胡同（光 [1,1,1,1] 这种就要多跑 4 倍递归）。所以写反不是「答案错」，而是「白费力、跑得慢」。标准写法永远用 not used[i-1]，让重复在同层最左边就被剪掉，最省。

几个高频追问，记住答法。

迁移阶梯：学会这刀剪枝后，去做 LC90 子集 II、LC40 组合总和 II——都是「排序 + 同层跳重复」的同一招。想不通时点右下角问问小欧。

边界三连：边界三连：全相同、无重复、多组重复，各跑一遍心里有底。