题解 | #56.有重复项数字的全排列#

用一个临时数组path存储排列的情况，用一个数组used表示数组中每个元素的访问情况

• 终止条件：临时数组中选取了n个元素，将其加入到结果中

• 本级任务：选择一个元素push到临时数组。已经加入的元素不能再加入(通过used数组帮助)。为了去除重复元素的影响，如果当前元素num[i]与num[i-1]相同且num[i-1]没有使用过，也不要将其纳入

  例子：1,2,2,3

  选取1，选取2，然后2和3排列有23和32情况，

  选取1，选取第二个2，由于num[2]==num[1] && !num[1]=true，所以直接continue,避免了重复情况，虽然如此，但是，我还是不太理解这个判断条件，

/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
 function permuteUnique( num ) {
  num = num.sort((a,b)=>a-b);//数组进行排序
  
  let result = [];//结果数组
  let path = [];//临时临时排列的数组
  let used = [];
  function backTrack(num){
    if(path.length == num.length){
      result.push([...path]);
      return;
    }
    for(let i=0; i<num.length; i++){//遍历所有元素选取一个加入
      if(i>0 && num[i]==num[i-1] && !used[i-1])//当前的元素num[i]与同⼀层的前⼀个元素num[i-1]相同且num[i-1]已经⽤过了
        continue;
      if(!used[i]){//如果该元素未被使用
        path.push(num[i]);
        used[i] = true;//标记为使⽤过
        backTrack(num);
        path.pop();//回溯
        used[i] = false;
      }
    }
  }
  
  backTrack(num);
  return result;
}