Leetcode 90 Subsets II

triplebee

发布于 2018-01-12 14:59:08

5160

发布于 2018-01-12 14:59:08

文章被收录于专栏：计算机视觉与深度学习基础

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

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

求给定数组的全部子集，可能有重复元素

DFS解决，先排序，对于每一个元素，可以选择使用，但是若不使用，则需要将和它值相同的元素全部移除。

class Solution {
public:
    void dfs(vector<vector<int>>& res,vector<int> nums,vector<int> now)
    {
        if(nums.size()==0)
        {
            res.push_back(now);
            return ;
        }
        vector<int> temp=now;
        int back=nums[nums.size()-1];
        nums.pop_back();
        now.push_back(back);
        dfs(res,nums,now);
        while(nums.size()>0 && nums[nums.size()-1]==back) nums.pop_back();//移除不使用的元素
        dfs(res,nums,temp);
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> now;
        sort(nums.begin(),nums.end());
        dfs(res,nums,now);
        return res;
    }
};

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

原始发表：2016-09-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs