0090.子集 II

https://leetcode.cn/problems/subsets-ii/

方法一：回溯

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

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	ans, n := [][]int{}, len(nums)
	var backtrack func(values []int, start int)
	backtrack = func(values []int, start int) {
		ans = append(ans, append([]int{}, values...))
		for i := start; i < n; i++ {
			if i > start && nums[i-1] == nums[i] {
				continue
			}
			values = append(values, nums[i])
			backtrack(values, i+1)
			values = values[:len(values)-1]
		}
	}
	backtrack([]int{}, 0)
	return ans
}