Subsets - recursion backtracking bit manipluation

subsets.cpp

// Firsrt appraoch
#include<bits/stdc++.h>
using namespace std;

void another(int I,vector<int> &temp,set<vector<int>> &ans,int A[],int n){
    vector<int> x = temp;
    sort(x.begin(),x.end());
    ans.insert(x);
    for(int i=I;i<n;i++){
        temp.push_back(A[i]);
        another(i+1,temp,ans,A,n);
        temp.pop_back();
    }
}

int main()
 {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int A[n];
	    for(int i=0;i<n;i++){
	        cin>>A[i];
	    }
	    vector<int> temp;
	    set<vector<int>> ans;
	    another(0,temp,ans,A,n);
	    for(auto it = ans.begin();it!=ans.end();it++){
	        cout<<"(";
	        int n = (*it).size();
	        for(int i=0;i<n-1;i++){
	            cout<<(*it)[i]<<" ";
	        }
	        if(n!=0)
	            cout<<(*it)[n-1];
	        cout<<")";
	    }
	    cout<<"\n";
	}
	return 0;
}

// Second approach
#include<bits/stdc++.h>
using namespace std;
int main()
 {
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	//code
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i=0;i<n;i++)    cin>>arr[i];
	  sort(arr,arr+n);
	  set<vector<int> >s;
	  
	  for(int i=0;i<pow(2,n);i++){
	      vector<int> v;
	      for(int j=0;j<n;j++){
	          if(i&(1<<j)){
	              v.push_back(arr[j]);
	          }
	      }
	      s.insert(v);
	  }
	 
	 for(auto x:s){
	   cout<<"(";
	   vector<int> v=x;
	   int n=v.size();
	   for(int i=0;i<n;i++){
	     cout<<v[i];
	     if(i!=n-1)cout<<" ";
	   }
	   cout<<")";
	 }
	 
	 cout<<endl;   
	}
	return 0;
}

Given an array of integers that might contain duplicates, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. The subsets must be sorted lexicographically.

Input:
2
3
1 2 2
4
1 2 3 3
Output:
()(1)(1 2)(1 2 2)(2)(2 2)
()(1)(1 2)(1 2 3)(1 2 3 3)(1 3)(1 3 3)(2)(2 3)(2 3 3)(3)(3 3)

First approach:
In this I used backtracking. We maintain a set of vectors ans, and store each intermediate subarray in this set. In the auxiliary recursive function, a for loop iterates over the array, and each time insert it into a temp vector. Then the function is called again with the current index. This temp is inserted in ans. When the recursive returns then the element is removed from the vector and the for loop inserts the next element. IN this way each of the 2^N combinations is traversed.

Second approach:
Here we used bit manipulation. Here for the size of the array (n), we iterate the power set of n times. Let's say n=3 then 2^3=8. Representing 1 to 8 values in binary gives 000,001,010,011,100,101,110,111. Interestingly, by taking the array element where the bit is set 1 we get al the subsets of the array. Thus if we iterate over the power set and for each of the numbers between 1 and 2^n we take the element from the original array which has a set bit gives us all the subsets.

i&(1<<j) : This is used to select jth bit if it is in i.
i|(1<<j) : This is used to set jth bit in i.
i^(1<<j) : This is used to erase jth bit in i if it is set.