LeetCode-90. 子集 II - sheep44044的小站

回溯#

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

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

示例 1：

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

示例 2：

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

手撕

思路:这里很像 47. 全排列 II 的情况，本身不需要used，但是需要判断不同的情况，像1 2 2和1 2的不同，所以需要判断前面的数是否使用，所以引入used

1
func subsetsWithDup(nums []int) [][]int {
2
    sort.Ints(nums)
3

4
    res := [][]int{}
5
    path := []int{}
6
    used := make([]bool, len(nums))
7

8
    var backtrack func(index int)
9
    backtrack = func(index int) {
10
        res = append(res, append([]int(nil), path...))
11

12
        for i := index; i < len(nums); i++ {
13
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
14
                continue
15
            }
16

17
            path = append(path, nums[i])
18
            used[i] = true
19
            backtrack(i+1)
20
            path = path[:len(path)-1]
21
            used[i] = false
22
        }
23
    }
24

25
    backtrack(0)
26
    return res
27
}