[46] 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

⁠ [1,2,3],

⁠ [1,3,2],

⁠ [2,1,3],

⁠ [2,3,1],

⁠ [3,1,2],

⁠ [3,2,1]

]

全排列问题，使用暴力回溯法解题，输出整个树的所有可能。

每次遍历时，控制剩余元素可选范围即可。

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  backtrack(nums);
  return res;

  function backtrack(rest: number[]) {
    if (rest.length === 0) {
      res.push([...path]);
      return;
    }
    rest.forEach((num, index) => {
      // 做选择
      path.push(num);
      // 回溯
      rest.splice(index, 1);
      backtrack(rest);
      // 取消选择
      rest.splice(index, 0, num);
      path.pop();
    });
  }
}