全排列 II 图解题解

这道题到底在问什么

nums

[2, 1, 1]

输出

[1,1,2] · [1,2,1] · [2,1,1]

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3笨办法：照全排列排出全部 n! 条，再丢进 set 去掉重复。可重复越多，白排的越多，纯属浪费。我们要在生成时就不排重复的。
2. 4先把数组排序，让相同的数挨在一起。回溯时仍是「选择→递归→撤销」，只多一刀剪枝：在同一层，如果这个数和左边那个一样、而左边那个还没被选，就跳过它。
3. 5nums = [2,1,1]，两个 1 被 2 隔开原始输入是 [2, 1, 1]。注意：两个 1 现在被 2 隔在了两头。这样剪枝那刀「看左边一个是不是同值」就判不出来——所以第一步必须先排序。
4. 6nums.sort() → [1,1,2]执行 nums.sort()：[2,1,1] 变成 [1, 1, 2]，下标 0 和下标 1 这两个 1 现在紧挨着了。看，2 挪到了最右边——这就是排序真正干的活。
5. 7nums = [1,1,2]，path 空现在从排好序的 [1, 1, 2] 开始回溯。path 空，三个数都没用过，res 空。
6. 8path = [1]第一层先选下标 0 的 1：标记已用，放进 path。path = [1]。
7. 9path = [1,1]第二层来到下标 1 的 1。它和左边一样，但左边那个 used[0] 是 True（在用），不跳过。选它，path = [1, 1]。
8. 10res ← [1,1,2]第三层只剩 2，凑满 [1, 1, 2]，记下第一条 [1,1,2]。然后开始回溯。
9. 11path = [1]撤销 2、再撤销下标1的 1，退回 path = [1]。第二层换 2 试试。
10. 12path = [1,2]第二层选 2。path = [1, 2]。第三层只剩下标1的 1 了。
11. 13res ← [1,2,1]第三层选下标1的 1，凑满 [1, 2, 1]，记下第二条 [1,2,1]。以下标0的 1 开头的排列全找完了。
12. 14path 空，used 全 False继续撤销，退回 path 空。现在第一层准备换下一个数——轮到下标 1 的 1 了。注意看下面这一帧。
13. 15i=1 的 1：左边同值且 used[0]=False → 跳过第一层轮到下标 1 的 1。它和下标 0 的 1 相同，而下标 0 的 used 是 False（刚撤销、本层没在用）——这正是要跳过的情形。它打头能排出的 [1,1,2]、[1,2,1] 刚才下标0的 1 已经排过了，再排就重复。直接跳过。
14. 16path = [2]跳过那个 1，第一层选 2。path = [2]。剩下两个 1。
15. 17path = [2,1]第二层选下标 0 的 1。path = [2, 1]。
16. 18res ← [2,1,1]第三层选下标1的 1（它的 used[0]=True，不跳），凑满 [2, 1, 1]，记下第三条 [2,1,1]。
17. 19回到 [2]，第二层下标1的 1 又被跳过撤回 path = [2]，第二层想换下标 1 的 1。可它和下标 0 的 1 相同、且 used[0]=False，又跳过。这条分支到头了。
18. 203 种不重复排列[1,1,2] · [1,2,1] · [2,1,1] 三条，不重不漏。没有那刀剪枝，会多出一份重复的 [1,1,2] 和 [1,2,1]。
19. 23去重的关键不在结果端，而在生成端：同一层里，相同的数只让最左边那个去打头。
20. 25若写成 used[i-1] 才跳：第一层先选下标0的 1把 not 漏掉、写成「used[i-1] 为 True 才跳」会怎样？跟着跑一遍。第一层下标 0 的 1：i=0 没左邻，照常选，path = [1]。
21. 26下标1的 1：左边 used[0]=True → 写反的条件把它跳了第二层轮到下标 1 的 1，此刻 used[0]=True。写反的条件「used[i-1] 为 True 才跳」在这里触发了——把它叉掉。注意：正确的 not 版本，这一步是要选的；两版正好跳的时机相反。
22. 27写反 → 结果照样 3 条，只是绕了更多死路绕来绕去，写反版最后居然也凑出了对的 3 条——结果不错！但它一路上多撞了好几次死胡同（光 [1,1,1,1] 这种就要多跑 4 倍递归）。所以写反不是「答案错」，而是「白费力、跑得慢」。标准写法永远用 not used[i-1]，让重复在同层最左边就被剪掉，最省。
23. 31学会这刀剪枝后，去做 LC90 子集 II、LC40 组合总和 II——都是「排序 + 同层跳重复」的同一招。想不通时点右下角问问小欧。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def permuteUnique(self, nums):
        nums.sort()
        n = len(nums)
        used = [False] * n
        ans, path = [], []
        def dfs():
            if len(path) == n:
                ans.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs()
                path.pop()
                used[i] = False
        dfs()
        return ans

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    void dfs(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) { ans.push_back(path); return; }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true; path.push_back(nums[i]);
            dfs(nums, used);
            path.pop_back(); used[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        dfs(nums, used);
        return ans;
    }
};

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    void dfs(int[] nums, boolean[] used) {
        if (path.size() == nums.length) { ans.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true; path.add(nums[i]);
            dfs(nums, used);
            path.remove(path.size() - 1); used[i] = false;
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, new boolean[nums.length]);
        return ans;
    }
}

nums.sort()                       # ① 先排序，让重复挨着
def backtrack(path):
    if 满足结束条件:
        res.append(path[:])           # 注意 [:] 拷贝
        return
    for i in range(n):
        if used[i]: continue          # 排列才需要：选过的跳
        if i > 0 and nums[i] == nums[i-1] \
                and not used[i-1]: continue   # ② 同层跳重复
        做选择(i)                      # used=True, append
        backtrack(path)
        撤销选择(i)                    # pop, used=False

sort(nums.begin(), nums.end());            // ① 先排序
void backtrack(vector<int>& path) {
    if (满足结束条件) { res.push_back(path); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;                 // 选过的跳
        if (i > 0 && nums[i] == nums[i-1]
                  && !used[i-1]) continue;     // ② 同层跳重复
        做选择(i);                            // used=true, push
        backtrack(path);
        撤销选择(i);                          // pop, used=false
    }
}

Arrays.sort(nums);                         // ① 先排序
void backtrack(List<Integer> path) {
    if (满足结束条件) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;                 // 选过的跳
        if (i > 0 && nums[i] == nums[i-1]
                  && !used[i-1]) continue;     // ② 同层跳重复
        做选择(i);                            // used=true, add
        backtrack(path);
        撤销选择(i);                          // remove, used=false
    }

复杂度

面试官可能追问