Miscellaneous

Problem
Given a set with ‘n’ elements, print subsets of all possible sizes.
Suppose we are given a set { 1, 2, 3 }
Possible subsets :: { 1 }  |  { 1, 2 }  |  { 1, 2, 3 }  |  { 1, 3 }  |  { 2 }  |  { 2, 3 }  |  { 3 }  |  { }

Solution
We will iterate over the set elements and find out all possible subsets recursively with the current set element as the first element of the subsets. Once the iteration of the set is over, we have found different subsets starting with each set element. See the implementation below.

```#include<iostream>
using namespace std;

// print the subset
void printSet(int set[],int size) {
cout<<"\n{ ";
int i;
for(i=0;i<size;i++) {
cout<<set[i];
if (i < size) {
cout<<",";
}
}
cout<<" }";
}

// recursively compute subset elements for subsets of all possible sizes
void subsets(int set[],int start,int end,int subset[],int index) {
printSet(subset,index);
int i;
for(i=start;i<=end;i++) {
subset[index] = set[i];
subsets(set,start+1,end,subset,index+1);
start += 1;
}
}

// generate subsets of all sizes
void generateSubsets(int set[],int size) {
int i,j;
int subset[size]; //stores the subset elements
for(i=0;i<size;i++) {
int start = i+1;
int end = size-1;
// first element is the current index
subset[0] = set[i];
// compute other elements of all the subsets with first element as set[i]
subsets(set,start,end,subset,1);
}
// print the NULL set
cout<<"\n{ }";
}

// main
int main() {
int set[] = {1,2,3,4};
int size = sizeof(set)/sizeof(set[0]);
cout<<"\nAll possible subsets are :-\n";
generateSubsets(set,size);
cout<<endl;
}```