package list

// Problem Definition: https://leetcode.cn/problems/permutations/
func permute(nums []int) (ret [][]int) {
	var track []int
	used := make([]bool, len(nums))

	var backtrack func()
	backtrack = func() {
		if len(track) == len(nums) {
			tmp := make([]int, len(nums))
			copy(tmp, track)
			ret = append(ret, tmp)
			return
		}

		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue
			}
			used[i] = true
			track = append(track, nums[i])
			backtrack()
			track = track[:len(track)-1]
			used[i] = false
		}
	}

	backtrack()

	return
}