47. Permutations II

[Tcdian]

47. Permutations II

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

Example

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const result = [];
    const permutation = [];
    const permutationCache = new Set();
    const indexCache = new Set();
    backtracking();
    return result;

    function backtracking() {
        if (permutation.length === nums.length) {
            if (!permutationCache.has(permutation.join(','))) {
                result.push([...permutation]);
                permutationCache.add(permutation.join(','));
            }
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (!indexCache.has(i)) {
                permutation.push(nums[i]);
                indexCache.add(i);
                backtracking();
                permutation.pop();
                indexCache.delete(i);
            }
        }
    }
};

• TypeScript Solution

function permuteUnique(nums: number[]): number[][] {
    const result: number[][] = [];
    const permutation: number[] = [];
    const permutationCache: Set<string> = new Set();
    const indexCache: Set<number> = new Set();
    backtracking();
    return result;

    function backtracking() {
        if (permutation.length === nums.length) {
            if (!permutationCache.has(permutation.join(','))) {
                result.push([...permutation]);
                permutationCache.add(permutation.join(','));
            }
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (!indexCache.has(i)) {
                permutation.push(nums[i]);
                indexCache.add(i);
                backtracking();
                permutation.pop();
                indexCache.delete(i);
            }
        }
    }
};