56. 有重复项数字的全排列

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

示例

输入：
[1,1,2]
返回值：
[[1,1,2],[1,2,1],[2,1,1]]

答案

var permute = function(nums) {
  let res = [];
  let used = [] // 标记使⽤：确定唯一性

  function backTrace(path) { // path排列的数组
    if(path.length === nums.length) return res.push(path.slice()); // 数组

    // 遍历所有元素选取一个加入
    for (let i = 0; i < nums.length; i++) {
      //当前的元素num[i]与同⼀层的前⼀个元素num[i-1]相同且num[i-1]已经⽤过了
      if( i >0 && nums[i] == nums[i-1] && !used[i-1] ){continue}
      //如果该元素未被使用
      if(!used[i]){
        path.push(nums[i]);
        used[i] = true // 标记为使⽤过
        backTrace(path);
        path.pop(); // 回溯
        used[i] = false
      }
        console.log(used)
    }
  }

  backTrace([]);

  return res;
};

var str = [1, 1, 2]
console.log(permute(str))