解题思路

与子集(LC79)不同的是数组中有重复的元素，题目要求我们的解集中不包含重复子集，有两种解法。

  1. 哈希表
  2. 排序

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = [[]]
        def dfs(startIndex: int, path: list[int]):
            if startIndex == len(nums): return

            for i in range(startIndex, len(nums)):
                if i > startIndex and nums[i - 1] == nums[i]: continue

                path.append(nums[i])
                result.append(path.copy())
                dfs(i + 1, path)
                path.pop()
        
        dfs(0, [])
        return result

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> path;
        result.push_back(path);

        backtracking(0, result, path, nums);
        return result;
    }

    void backtracking(int startIndex, vector<vector<int>> &result, vector<int> &path, vector<int> &nums) {
        if (startIndex == nums.size()) return;

        for (int i = startIndex; i < nums.size(); ++i) {
            if (i > startIndex && nums[i] == nums[i - 1]) continue;

            path.push_back(nums[i]);
            result.push_back(path);
            backtracking(i + 1, result, path, nums);
            path.pop_back();
        }
    }
};

Go

var result [][]int
func subsetsWithDup(nums []int) [][]int {
    result = [][]int{}
    result = append(result, []int{})
    sort.Ints(nums)
    backtracking(0, []int{}, nums)
    return result
}

func backtracking(startIndex int, path []int, nums []int) {
    for i := startIndex; i < len(nums); i++ {
        if i > startIndex && nums[i] == nums[i - 1] {continue}
        path = append(path, nums[i])
        t := make([]int, len(path))
        copy(t, path)
        result = append(result, t)
        backtracking(i + 1, path, nums)
        path = path[:len(path) - 1]
    }
}