46-全排列.md

46-全排列

原题

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1] 输出：[[0,1],[1,0]]

输入：nums = [1] 输出：[[1]]

const permute = (nums) => {
  const res = [];
  const used = {};

  const backtrack = (path) => {
    if (path.length === nums.length) {
      // 1. 这里是使用的 path.slice() 不能直接使用 path
      res.push(path.slice());
      return;
    }

    for (const num of nums) {
      if (used[num]) {
        continue;
      }

      used[num] = true;

      // 2. 这里先push，backtrack之后再pop，是使用回溯方法的经典操作
      path.push(num);
      backtrack(path);
      path.pop();

      used[num] = false;
    }
  };

  backtrack([]);
  return res;
};

let result = permute([1, 2, 3]);
console.log(result);

有些注意点需要特别说明，在上面的代码中，有两个地方在上面的代码中已经标注了 可以换一下，比如如下

const permute = (nums) => {
  const res = [];
  const used = {};

  const backtrack = (path) => {
    if (path.length === nums.length) {
      // 1. 这里就可以直接使用 path 了，不用 slice 的操作了
      res.push(path);
      return;
    }

    for (const num of nums) {
      if (used[num]) {
        continue;
      }

      used[num] = true;
      // 2. 这里直接使用 concat，这种方式就不会影响当前的 path了，就不用再需要 push/pop 的操作了
      backtrack(path.concat(num));
      used[num] = false;
    }
  };

  backtrack([]);
  return res;
};

let result = permute([1, 2, 3]);
console.log(result);

子集、全排列这些，其实都是设定一个递归函数，然后在函数里面进行 for 循环，设置当前这个数是否已经被循环过了 然后再进行递归的时候，把没有循环过的数据再添加进来，组成一个新的结果，看当前这个结果是否符合要求， 如果符合要求，就添加到结果集里面

这种还有其他的办法，就是那个转化成那个 const a = [['a', 'b', 'c'], ['d', 'f', g]] 生成结果是 ad / af / ag ... 这个问题 就只需要把上面那个的输入 [1,2,3] 先转换成 [[1,2,3], [1,2,3], [1,2,3]]，然后接着做就可以了