全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

  • 输入：nums = [1,1,2]
    输出：
    [[1,1,2],
    [1,2,1],
    [2,1,1]]

  • 输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var permuteUnique = function(nums) {
    const res = [];
    const used = new Array(nums.length);
    nums.sort((a, b) => a - b); // 升序排序

    const helper = (path) => {
        if (path.length == nums.length) { // 个数选够了
            res.push(path.slice());       // path的拷贝 加入解集
            return;                       // 结束当前递归分支
        }

        for (let i = 0; i < nums.length; i++) { // 枚举出所有的选择
            if (used[i]) {                      // 这个数使用过了，跳过。
                continue;
            }
            if (i - 1 >= 0 && nums[i - 1] == nums[i] && !used[i - 1]) { // 避免产生重复的排列
                continue;
            }
            path.push(nums[i]); // make a choice
            used[i] = true;     // 记录路径上做过的选择
            helper(path);       // explore，基于它继续选，递归
            path.pop();         // undo the choice
            used[i] = false;    // 也要撤销一下对它的记录
        }
    };

    helper([]);
    return res;
};