// 链接：https://leetcode-cn.com/problems/permutations
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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

// console.log(permute([1,2,3]))
function permute (nums) {
  if (nums.length === 1) return [nums]
  const arr = nums.slice()
  const last = arr.pop()
  const subs = permute(arr)
  return [].concat(...subs.map(v => insert(v, last)))
}

// console.log(insert([1, 2], 3))
function insert (arr, v) {
  const result = []
  for (let i = 0; i <= arr.length; i++) {
    const t = arr.slice()
    t.splice(i, 0, v)
    result.push(t)
  }
  return result
}