essay
hot100-全排列
#算法
hot100——全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
解法
func permute(nums []int) [][]int {
res := make([][]int, 0)
n := len(nums)
used := make([]bool, n)
path := make([]int, 0, n)
backtrack(&res, nums, path, used)
return res
}
// backtrack 是核心递归函数
// 参数：
// res - 指向结果集的指针，用于收集完整排列
// nums - 原始数组（只读）
// path - 当前已选数字的序列（切片，每次递归传递副本但底层数组共享）
// used - 标记数组，记录 nums 中每个数字是否已被使用
func backtrack(res *[][]int, nums []int, path []int, used []bool) {
// 递归终止：path 长度等于原数组长度，说明找到一个完整排列
if len(path) == len(nums) {
// 拷贝一份 path 加入结果集，避免后续修改影响已保存的排列
tmp := make([]int, len(path))
copy(tmp, path)
*res = append(*res, tmp)
return
}
// 遍历所有数字，尝试填入当前位置
for i := 0; i < len(nums); i++ {
if used[i] {
continue // 跳过已使用的数字
}
// 做选择
used[i] = true
path = append(path, nums[i])
// 递归进入下一层
backtrack(res, nums, path, used)
// 撤销选择（回溯）
path = path[:len(path)-1]
used[i] = false
}
}