LeetCode 90：Subsets II

LeetCode 90：Subsets II

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

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

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

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

  Subscribeto see which companies asked this question

  這題有重復元素，但本質上，跟上題很類似，也可以用類似的方法處理：

  class Solution {
  public:
  	vector> subsetsWithDup(vector& nums) {
  		vector> ans(1, vector());
  		sort(nums.begin(), nums.end());
  		
  		int pre_size = 0;
  		for (int i = 0; i < nums.size(); i++)
  		{
  			int n = ans.size();
  			for (int j = 0; j < n; j++) //第二個for循環是為了求得包含nums[i]的所有子集  
  			{
  				if (i == 0 || nums[i] != nums[i -1] || j>=pre_size)
  				{
  					ans.push_back(ans[j]); //在尾部重新插入ans已經存在的子集  
  					ans.back().push_back(nums[i]); //將nums[i]添加進去 
  				}
  			}
  			pre_size = n;
  		}
  		return ans;
  	}
  };