47. Permutations II（js）

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
题意：找出有重复项的数组的所有排列组合
代码如下：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    if(nums==null || nums.length===0) return nums;
    var res=new Set();
    var curr=[];
    var used=[];
    nums=nums.sort(function(a,b){ return a-b;})
    backtrack(res,used,curr,nums);
    return [...res];
};
var backtrack=function(res,used,curr,nums){
    if(curr.length===nums.length) {
        res.add([...curr]);
    }else {
        for(var i=0;i<nums.length;i++){
            if(used[i]) continue;
            if(i>0 && nums[i-1]===nums[i] && !used[i-1]) continue;
            curr.push(nums[i]);
            used[i]=true;
            backtrack(res,used,curr,nums);
            used[i]=false;
            curr.splice(curr.length-1,1);
        }
    }
}