题目描述#

给定一个不含重复数字的数组 nums，要求返回它的所有可能全排列。答案可以按任意顺序返回。

全排列要求每个数字都使用一次，并且不同顺序算作不同结果。

思路#

这题可以把排列看成“给每个位置选一个数”。path[i] 表示排列中第 i 个位置放什么数字，所以回溯函数 dfs(i) 就是在决定第 i 个位置要填 nums 里的哪个数。嘿嘿，像是给一排空相框挑照片，每张照片只能出现一次，摆法不同就是不同相册～

为了避免同一个数字被重复使用，代码用 onPath 记录 nums 中每个下标的数字是否已经在当前路径里。每到一层递归，就遍历所有数字，如果某个数字还没被使用，就把它填到 path[i]，并把对应的 onPath[j] 标记为 true，然后递归处理下一个位置。

当 i == n 时，说明 path 的每个位置都已经填好，此时得到一个完整排列。这里加入答案时使用 append([]int(nil), path...) 复制一份路径，因为 path 后续还会继续被回溯过程修改。没错没错，回溯保存答案时一定要拍“定格照”，不然下一秒现场就变样啦～

递归返回后，需要把 onPath[j] 改回 false，也就是恢复现场，让这个数字可以被其他分支继续使用。全排列一共有 n! 个结果，每个结果复制需要 O(n)，所以时间复杂度为 O(n * n!)；额外空间主要是 path、onPath 和递归栈，为 O(n)，不计返回结果。

思维边界#

• 位置视角：每一层递归负责填 path 的一个位置，而不是直接处理某个数字。
• 使用标记：onPath 记录哪些下标已经在当前排列中，避免同一个元素重复出现。
• 终止条件：当 i == n 时，说明已经形成一个完整排列，可以加入答案。
• 路径复制：保存答案时必须复制 path，否则后续回溯会覆盖已保存的排列。
• 恢复现场：递归结束后将 onPath[j] 还原为 false，让其他分支能继续选择该数字。

代码#

func permute(nums []int) [][]int {
	n := len(nums)
	path := make([]int, n)
	onPath := make([]bool, n)
	ans := [][]int{}
	// 枚举 path[i] 填 nums 的哪个数
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, append([]int(nil), path...))
			return
		}
		for j, on := range onPath {
			if !on {
				path[i] = nums[j]
				onPath[j] = true
				dfs(i + 1)
				onPath[j] = false
			}
		}
	}

	dfs(0)
	return ans
}