全排列 II 图解题解

这道题到底在问什么

输入

nums=[1,1,2]

输出

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

最优解：一步一步想明白

1. 3记住这条去重判断「同层、相同值、前一个没用就跳过」,下面每一帧都在套它。
2. 4开局:nums 已排好序 [1,1,2],path 是空的,三个数都没用过(白色),结果 res 也是空。每一层从头扫候选,挑一个没用过的放进 path——但碰到重复值要小心。
3. 5选中没用过的 1(第 0 个):标记它为已用、放进 path。现在 path = [1],往下一层递归。
4. 6这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
5. 7选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [1,1],往下一层递归。
6. 8这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
7. 9这一层从头扫:第 1 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
8. 10选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [1,1,2],往下一层递归。
9. 11path 凑满了 3 个数 —— 记下这个排列 [1,1,2]。然后开始往回退(回溯),去试别的可能。
10. 12回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
11. 13回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
12. 14选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [1,2],往下一层递归。
13. 15这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
14. 16选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [1,2,1],往下一层递归。
15. 17path 凑满了 3 个数 —— 记下这个排列 [1,2,1]。然后开始往回退(回溯),去试别的可能。
16. 18回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
17. 19这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
18. 20回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
19. 21回溯:把第 0 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
20. 22去重剪枝:第 1 个数 1 和它前面那个相等(都是 1),而前一个这层没用(白色)——说明前一个等值数刚在本层试过又撤销了,再选这个会排出一模一样的排列。打 ✗ 跳过。
21. 23选中没用过的 2(第 2 个):标记它为已用、放进 path。现在 path = [2],往下一层递归。
22. 24选中没用过的 1(第 0 个):标记它为已用、放进 path。现在 path = [2,1],往下一层递归。
23. 25这一层从头扫:第 0 个数 1 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
24. 26选中没用过的 1(第 1 个):标记它为已用、放进 path。现在 path = [2,1,1],往下一层递归。
25. 27path 凑满了 3 个数 —— 记下这个排列 [2,1,1]。然后开始往回退(回溯),去试别的可能。
26. 28回溯:把第 1 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
27. 29这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
28. 30回溯:把第 0 个的 1 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。
29. 31去重剪枝:第 1 个数 1 和它前面那个相等(都是 1),而前一个这层没用(白色)——说明前一个等值数刚在本层试过又撤销了,再选这个会排出一模一样的排列。打 ✗ 跳过。
30. 32这一层从头扫:第 2 个数 2 已经在 path 里了(used 标灰),打个 ✗ 跳过,不能重复用同一个位置。
31. 33回溯:把第 2 个的 2 移出 path、把它的 used 标记撤销(重新变白,后面别的分支还能用它)。回到上一层继续试下一个候选。

⚠️ 容易写错的地方

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

def permuteUnique(nums):
    nums.sort()                # 排序,让相同值相邻
    res, n = [], len(nums)
    used = [False] * n
    path = []
    def backtrack():
        if len(path) == n:
            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          # 同层去重
            used[i] = True; path.append(nums[i])
            backtrack()
            path.pop(); used[i] = False  # 撤销
    backtrack()
    return res

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    void bt(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) { res.push_back(path); return; }
        for (int i = 0; i < 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]);
            bt(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);
        bt(nums, used);
        return res;
    }
};

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);               // 排序,让相同值相邻
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used);
        return res;
    }
    void backtrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.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]);
            backtrack(nums, used);
            path.remove(path.size() - 1); used[i] = false;  // 撤销
        }
    }
}

复杂度

面试官可能追问