全排列

难度：⭐⭐⭐ 面试高频

考点

• 回溯模板
• used 数组标记访问状态
• 字节面试高频题

题目描述

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

函数签名

func permute(nums []int) [][]int

示例

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

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

要求

1. 使用回溯法
2. 结果数量应为 n!

提示

• 用 used[] 数组标记哪些数字已经选过
• 选择 → 递归 → 撤销选择
• path 长度等于 nums 长度时收集结果
• 注意 append 后需要 copy 再加入 result

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func permute(nums []int) [][]int {
	var result [][]int
	used := make([]bool, len(nums))
	var backtrack func(path []int)
	backtrack = func(path []int) {
		if len(path) == len(nums) {
			tmp := make([]int, len(path))
			copy(tmp, path)
			result = append(result, tmp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			backtrack(path)
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	backtrack(nil)
	return result
}