0047.全排列 II

方法一：回溯

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

func permuteUnique(nums []int) [][]int {
	ans, n := [][]int{}, len(nums)
	sort.Ints(nums)
	var backtrack func(vals []int, used []bool)

	backtrack = func(vals []int, used []bool) {
		if len(vals) == n {
			ans = append(ans, append([]int{}, vals...))
			return
		}

		i := 0
		for ; i < n; i++ {
			if !used[i] {
				break
			}
		}
		for start := i; i < n; i++ {
			if used[i] || (i != start && nums[i] == nums[start]) {
				continue
			}
			start = i
			vals, used[i] = append(vals, nums[i]), true
			backtrack(vals, used)
			vals, used[i] = vals[:len(vals)-1], false
		}
	}
	backtrack([]int{}, make([]bool, n))
	return ans
}