0046.全排列

https://leetcode.cn/problems/permutations/

方法一：回溯

时间复杂度 $O(n \times n!)$，空间复杂度 $O(n)$。

func permute(nums []int) [][]int {
	ans, used, n := make([][]int, 0), make([]bool, len(nums)), len(nums)
	var backtrack func(vals []int)
	backtrack = func(vals []int) {
		if len(vals) == n {
			ans = append(ans, append([]int{}, vals...))
			return
		}
		for i := 0; i < n; i++ {
			if used[i] {
				continue
			}
			vals, used[i] = append(vals, nums[i]), true
			backtrack(vals)
			vals, used[i] = vals[:len(vals)-1], false
		}
	}
	backtrack([]int{})
	return ans
}