题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例：

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

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

解答 & 代码

[中等] 78. 子集
递归回溯，和上面这题的区别就在于，本题数组 nums 中存在重复元素。
为了去重，需要先对数组 nums 进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过

class Solution {
private:
    vector<vector<int>> resultList;
    vector<int> curSet;
    void backTrack(vector<int>& nums, int start)
    {
        // 前序位置，每个节点的值都是一个子集
        resultList.push_back(curSet);

        int pre;
        for(int i = start; i < nums.size(); ++i)
        {
             // 改变二：剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if(i == start || nums[i] != pre)
            {
                curSet.push_back(nums[i]);
                backTrack(nums, i + 1);
                curSet.pop_back();
            }
            pre = nums[i];
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 改变一：先排序，让相同的元素靠在一起
        sort(nums.begin(), nums.end());
        backTrack(nums, 0);
        return resultList;
    }
};

复杂度分析：设整数数组 nums 有 n 个元素

时间复杂度：n 个元素，每个元素都可以选择放到子集里 or 不放到子集里，一共个状态，每个状态需要 O(n) 的时间构造子集
空间复杂度 O(n)：递归栈空间 = 子集的最大长度

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了 44.41% 的用户

hot 100

[中等] 90. 子集 II

题目

解答 & 代码