回溯：排列与去重（全排列）

一、面试常考点

1. 排列模板

使用 used 数组标记元素是否已在当前路径。

2. 去重关键

排序后结合 used[i-1] 判断同层重复。

二、细节介绍

1. 状态

path 记录当前排列。

2. 结束条件

path.length === nums.length。

三、示例代码

function permute(nums) {
  const res = []
  const path = []
  const used = Array(nums.length).fill(false)

  function dfs() {
    if (path.length === nums.length) {
      res.push([...path])
      return
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(nums[i])
      dfs()
      path.pop()
      used[i] = false
    }
  }

  dfs()
  return res
}

四、常用应用场景

1. 排序空间搜索

任务执行顺序探索。

2. 路径方案枚举

流程分支排列尝试。