90. 子集 II

mid

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

DFS 回溯

组合问题，跟子集Ⅰ的不同是包含重复元素了，得去重（采用排序的方式），保证同一层上不能有重复的元素，不同层是可以重复的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import "sort"

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	res := make([][]int, 0)
	subset := make([]int, 0)
	var dfs func(startIndex int)
	dfs = func(startIndex int) {
		res = append(res, append([]int{}, subset...))
		for i := startIndex; i < len(nums); i++ {
			if i > startIndex && nums[i] == nums[i-1] {
				// 去重
				continue
			}
			subset = append(subset, nums[i])
			dfs(i + 1)
			subset = subset[:len(subset)-1]
		}
	}
	dfs(0)
	return res
}