leetcode 90 子集II

题目

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

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

示例

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

解析

这道题和上一道的区别就是原始数据中有重复的元素，结果集中同一树枝的元素可以重复，但同一层的不可以重复；

func subsetsWithDup(nums []int) [][]int {
    var path []int
    var res [][]int
    sort.Ints(nums) //需要先排序，因为下面要比较相邻的两个元素
    backtracking(nums, 0, path, &res)
    return res
}

func backtracking(nums []int, startIndex int, path []int, res *[][]int) {
    //依然不需要终止条件
    temp := make([]int, len(path))
    copy(temp, path)
    *res = append(*res, temp)

    for i := startIndex; i < len(nums); i++ {
        if i > startIndex && nums[i] == nums[i-1] { //i>startIndex是用来判断同一树层的
            continue
        }

        path = append(path, nums[i])
        backtracking(nums, i+1, path, res)
        path = path[:len(path)-1]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24