力扣 46. 组合
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
方案一：递归，遍历每一种可能。
func permute(nums []int) (ans [][]int) {
n := len(nums)
// 存放当前选中的元素
chosen := make([]int, 0, n)
// 标记当前那个元素被使用了，因为是全排列，同一个元素只能出现一次
used := make([]bool, n)
// 递归函数
var recur func()
recur = func() {
// 如果元素已满则将 chosen 作深拷贝并保存结果
if len(chosen) == n {
tmp := make([]int, n)
copy(tmp, chosen)
ans = append(ans, tmp)
}
for i, v := range nums {
// 如果当前元素已被使用则跳过
if used[i] {
continue
}
// 标记当前元素（将其标记为已使用）
used[i] = true
// 将其加入选择结果
chosen = append(chosen, v)
// 执行递归
recur()
// 还原现场，避免干扰到其他递归分支
chosen = chosen[:len(chosen) - 1]
used[i] = false
}
}
// 开始递归
recur()
return
}
- 时间复杂度：O(n! * n)，因为一共有 n! 个状态，每个状态需要 O(n) 的时间复杂度（深拷贝），所以时间复杂度为 O(n! * n)。
- 空间复杂度：O(n + n)，因为栈深度为 n，chosen 长度为 n ，所以空间复杂度为 O(n + k)。