LeetCode 0090 - Subsets II

Reck Zhang

发布于 2021-08-11 10:52:20

1680

发布于 2021-08-11 10:52:20

文章被收录于专栏：Reck Zhang

Subsets II

Desicription

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],
  []
]

Solution

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res = {{}};
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size();) {
            int repeat_cnt = 0;
            while(repeat_cnt + i < nums.size() && nums[repeat_cnt+i] == nums[i])
                repeat_cnt++;
            int res_size = res.size();
            for(int j = 0; j < res_size; j++) {
                vector<int> currency = res[j];
                for(int k = 0; k < repeat_cnt; k++){
                    currency.push_back(nums[i]);
                    res.push_back(currency);
                }
            }
            i += repeat_cnt;
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除

duplicates