Subsets II in CPP

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

Before solving this problem, have a look at similar kind of problem Subsets.

Given a collection of numbers that might contain duplicates, return all possible unique permutations in C++

Similar to the subset 1 problem, we can solve this problem by 2 ways.
1. Iterative
2. Recursive/ Backtrack.

We shall discuss both of the solutions here.

So the only difference between the “subset” problem and this is that the duplicates are allowed in the input list.
Hence we do below 2 changes:

1. Sort the input array, so that the duplicate elements are placed next to each other.
2. Then we check if the previous element is same as present element, we skip that element.

Solution in C++

/*
* File     : get_subsets_II.cpp
*/
#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> get_subsets_with_dup_iterative(vector<int>& input_set) 
{
  sort(input_set.begin(), input_set.end());//change 1
  vector<vector<int>> result_set(1, vector<int>());
  int start = 0;
  int n = 0;
  for (int i = 0; i < input_set.size(); i++) 
  {
    start = ((i > 0) && (input_set[i] == input_set[i - 1])) ? n : 0;
    n = result_set.size();
    for (int j = start; j < n; j++) 
    {
      result_set.push_back(result_set[j]); 
      result_set.back().push_back(input_set[i]);
    }
  }
  return result_set;
}


void subsets(vector<int>& nums, int start, vector<int>& temp, vector<vector<int>>& final_set) 
{
  final_set.push_back(temp);
  for (int i = start; i < nums.size(); i++) 
  {
    if ((i == start) || (nums[i] != nums[i - 1]))  // change 2
    {
      temp.push_back(nums[i]);
      subsets(nums, i + 1, temp, final_set);
      temp.pop_back();
    }
  }
}


vector<vector<int>> get_subsets_with_dup_backtrack(vector<int>& nums) 
{
  sort(nums.begin(), nums.end()); // change 1
  vector<vector<int>> final_set;
  vector<int> temp;
  subsets(nums, 0, temp, final_set);
  return final_set;
}



int main()
{
  vector<int> input_set = {1, 2, 2};

  vector< vector<int> >result = get_subsets_with_dup_iterative(input_set);
  //vector< vector<int> >result = get_subsets_with_dup_backtrack(input_set);



  for (int i = 0; i < result.size(); i++)
  {
    for (int j = 0; j < result[i].size(); j++)
    {
      cout<< result[i][j]<<" ";
    }
    cout<<endl;
  }
}