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.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> sol; if (nums.size() == 0) { return sol; } sort(nums.begin(), nums.end()); sol.push_back(vector<int>()); int beginning = 0, size; for (int i = 0; i < nums.size(); i++) { size = sol.size();
// Handle duplicate elements. if (i != 0 && nums[i] == nums[i - 1]) { // Start from the beginning of last insertion round. beginning = size - beginning; } else { // Start from beginning. beginning = 0; } for (int j = beginning; j < size; j++) { vector<int> tmp = sol[j]; tmp.push_back(nums[i]); sol.push_back(tmp); } // Adjust beginning for the next iteration. beginning = size - beginning; } return sol; } };