46.全排列.md

46.全排列

/*
 * @lc app=leetcode.cn id=46 lang=typescript
 *
 * [46] 全排列
 */

// @lc code=start
function permute(nums: number[]): number[][] {}
// @lc code=end

解法 1: 递归

• 时间复杂度:

广度优先

function permute(nums: number[], n = 0): number[][] {
  if (nums.length === n) return [[]]

  let prevs = permute(nums, n + 1)
  const res = []
  for (const prev of prevs) {
    for (let i = 0; i < nums.length; i++) {
      const el = nums[i]
      if (!prev.includes(el)) {
        res.push([...prev, el])
      }
    }
  }

  return res
}

解法 2: 回溯

• 时间复杂度:

深度优先

function permute(nums: number[]): number[][] {
  const cache: { [key: number]: number } = {}
  let result: number[][] = []
  const backtrack = (nums: number[], path: number[] = [], depth: number = 0) => {
    if (nums.length === depth) {
      result.push(path)
      return
    }

    for (let i = 0; i < nums.length; i++) {
      const num = nums[i]
      if (!cache[num]) {
        cache[num] = 1
        backtrack(nums, [...path, num], depth + 1)
        cache[num] = 0
      }
    }
  }
  backtrack(nums)

  return result
}

解法 3: 迭代

function permute(nums: number[]): number[][] {
  let result: number[][] = [[]]

  for (let i = 0; i < nums.length; i++) {
    const tmp = result
    result = []
    for (let j = 0; j < nums.length; j++) {
      const el = nums[j]
      for (let k = 0; k < tmp.length; k++) {
        const arr = tmp[k]
        if (!arr.includes(el)) {
          result.push([...arr, el])
        }
      }
    }
  }

  return result
}

解法 4: 回溯 2

function permute(nums: number[], n = 0): number[][] {
  const backtrack = (nums: number[], start: number = 0, res: number[][] = []): number[][] => {
    if (start === nums.length) {
      res.push(nums)
      return res
    }

    for (let i = start; i < nums.length; i++) {
      ;[nums[start], nums[i]] = [nums[i], nums[start]]
      backtrack([...nums], start + 1, res)
      // 下面这行不加也可以生成正确的结果
      // 不过加上后属于比较正统的回溯,会更容易理解
      ;[nums[start], nums[i]] = [nums[i], nums[start]]
    }
    return res
  }

  return backtrack(nums)
}