46.Permutations

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const n = nums.length
  const path = Array(n).fill(0)
  const onPath = Array(n).fill(false)
  const ans = []

  // 枚举 path[i] 填 nums 的哪个数
  const dfs = (i) => {
    if (i === n) {
      ans.push(path.slice())
      return
    }
    // 枚举选哪个
    for (let j = 0; j < n; j++) {
      if (onPath[j]) {
        continue
      } else {
        onPath[j] = true
        path[i] = nums[j]
        dfs(i + 1)
        onPath[j] = false
        // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
      }
    }
  }
  dfs(0)
  return ans
}