package permutations

// 46. 全排列
// https://leetcode-cn.com/problems/permutations/

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	used := make([]bool, len(nums))
	res := make([][]int, 0)
	tmp := make([]int, 0)

	dfs(nums, tmp, &res, &used)

	return res
}

func dfs(nums []int, tmp []int, res *[][]int, used *[]bool) {
	if len(tmp) == len(nums) {
		*res = append(*res, append([]int{}, tmp...))
		return
	}

	for i := 0; i < len(nums); i++ {
		if !(*used)[i] {
			(*used)[i] = true
			tmp = append(tmp, nums[i])
			dfs(nums, tmp, res, used)
			tmp = tmp[:len(tmp)-1]
			(*used)[i] = false
		}
	}
}