90. 子集 II

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

解法一：排序 + 回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    var ans [][]int
    var tmp []int
    var backtracking func(idx int)
    backtracking = func(idx int) {
        ans = append(ans, append([]int(nil), tmp...))
        for i := idx; i < n; i++ {
            if i == idx || nums[i] != nums[i-1] {
                tmp = append(tmp, nums[i])
                backtracking(i + 1)
                tmp = tmp[:len(tmp)-1]
            }
        }
    }
    backtracking(0)
    return ans
}