[JavaScript知识库]leetcode——46. 全排列(Javascript)

一、题目地址

https://leetcode-cn.com/problems/permutations/

二、思路地址

https://www.bilibili.com/video/BV1up4y1s7yB?from=search&seid=6669046289158748468

三、具体代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

//回溯算法
var backTracing = function(result, list, nums, map) {
  //递归终止条件
  if(list.length === nums.length) {
      //不能直接result.push(list);因为这样会引起引用赋值,导致后面发生错误
      /* 
        使用slice()的原因是,在每一次list的长度等于nums的长度时,
        给每一个list每次创建不同的内存空间(即每一个list的内存地址不同),
        而slice() 就可以很好地做到这一点,这样就避免如果每一个list内存地址相同,
        而后续引起引用赋值,导致后续每一个list的值都发生了改变,所以仅仅是使用
        result.push(list);输出的结果就会是[[],[],[],[],[],[]]
        因此加了list.slice(0)这一步
       */
      result.push(list.slice(0));
      return;
  }
  for(let j=0; j<nums.length; j++) {
      if(map.get(nums[j]) === false) {
          list.push(nums[j]);
          map.set(nums[j], true);
          backTracing(result, list, nums, map);
          list.pop();
          map.set(nums[j], false);
      }
  }
}


var permute = function(nums) {
  /*  
      定义一个map表,用来标志数组的每一项是否加入了list,
      map的value值为true表示list的这一项,已加入list中,否则
      并没有加入
   */
  let map = new Map();    
  let result = [];//存放所有结果(即list)的数组
  let list = [];//存放每一项结果,最后需要把list转成字符串,再放入result中
  for(let i=0; i<nums.length; i++) {
      map.set(nums[i], false);
  }
  backTracing(result, list, nums, map);//核心代码,回溯算法,里面还采用了递归
  return result;
};