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

按照56题的思路可能更简单一点，和56题有重复项数字的全排列代码一样

function permute( num ) {
  
  let path = [];
  let res = [];
  let used = [];
  
  function traceTrack(){
    //path已经达到num长度时
    if(path.length == num.length){
      res.push([...path]);
      return;
    }
    for(let i=0; i<num.length; i++){
      if(i!=0 && num[i]==num[i-1] && !used[i-1])
        continue;
      
      if(!used[i]){
        path.push(num[i]);
        used[i] = true;
        traceTrack();
        used[i] = false;
        path.pop();
      }
    }
  }
  
  traceTrack();
  return res;
}

全排列就是对数组元素交换位置，使得每一种排列都可能出现

递归

• 终止条件：要交换的下标到了数组末尾，没有可交换的了，这就构成了一个排列情况，加入到结果数组。
• 本级任务：遍历从它开始的后续元素，每一个就与它交换依次位置 回溯：当1与3交换位置以后，如果2和4再交换位置的时候，我们只能得到3412，无法得到1432。这是因为1和3的交换在2和4交换的前面，递归过程中默认将后者看成前者的子问题，这时就需要回溯，交换回原来的位置。

代码都要背下来了，可是还是不太能理解😅😅😅😅😅😅😅😅，蚌埠住了

 function permute( num ) {
  if(num.length <= 1)
    return [num];
  
  let n = num.length;
  let ans = [];
  
  function swap(left,right){
    let temp = num[left];
    num[left] = num[right];
    num[right] = temp;
  }
  
  function permumation(index){
    if(index >= n){
      ans.push(num);
    }else{
      for(let j=index; j<n; j++){
        swap(index,j);
        permumation(index+1);
        swap(index,j);
      }
    }
  }
  
  permumation(0);
  return ans;
}