LeetCode: 90. Subsets II

题目描述

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题目大意： 求给定包含相同元素的集合的所有子集。

解题思路 —— 递归求解

直接递归求集合的子集，放在 set 中，去重。

递归求解子集: 求前 n-1 个数的子集， 前 n 个数的子集是不包含第 n 个数的子集(前 n-1 个数的子集) 和包含第 n 个数的子集(前 n - 1 个数的子集加上第n个数构成的集合)。

AC 代码

class Solution
{
private:
    // [start, end)
    set<vector<int>> subsetsWithDupRef(vector<int>& nums, int start, int end)
    {
        if(start >= end)
        {
            return {{}};
        }

        set<vector<int>> firstHalf = subsetsWithDupRef(nums, start, end-1);
        set<vector<int>> secondHalf;

        for(auto iter = firstHalf.begin(); iter != firstHalf.end(); ++iter)
        {
            vector<int> tmp = *iter;
            tmp.push_back(nums[end-1]);
            secondHalf.insert(tmp);
        }

        firstHalf.insert(secondHalf.begin(), secondHalf.end());

        return firstHalf;
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        set<vector<int>> subsets = subsetsWithDupRef(nums, 0, nums.size());
        return vector<vector<int>>(subsets.begin(), subsets.end());
    }
};