C++ Programming Code Examples C++ > Beginners Lab Assignments Code Examples Program to Generate All Pairs of Subsets Whose Union Make the Set Program to Generate All Pairs of Subsets Whose Union Make the Set - This algorithm generates all pairs of subsets whose union make the set. - The time complexity of this algorithm is O(n*2^n). - This algorithm takes the input of 'n' data element and prints unique subset pairs whose union gives the set. - For that, it generates 0 to 2^(n-1) bit random sequence of 0 or 1 using binary counting. - Print the elements in the pairs which have 1 or 0 at the corresponding indexes. - Exit. C++ Program to generate a random subset by coin flipping. #include<iostream> #include<math.h> #include<iomanip> using namespace std; // A function to print array element according to the code in the argument list. void print(char code[], int arr[], int n) { int j; cout<<"\t{ "; for(j = 0; j < n; j++) { // Print if the corresponding value is 1. if(code[j] == '1') cout<<arr[j]<<" "; } cout<<"}"; cout<<" { "; for(j = 0; j < n; j++) { // Print if the corresponding value is 0. // It will print the remaining elements which on union forms the superset. if(code[j] == '0') cout<<arr[j]<<" "; } cout<<"}\n"; } void GenUnionSet(int arr[], int n) { int j, r, l; char binary[n]; r = pow(2, n-1); for(j = 0; j < n; j++)binary[j] = '0'; for(j = 0; j < r; j++) { print(binary, arr, n); l=n-1; // Incrementing the binary value with each iteration. h: if(binary[l] == '0') binary[l] = '1'; else { binary[l] = '0'; l--; goto h; } } } int main() { int j, n; cout<<"\nEnter the number of element array have: "; cin>>n; int arr[n]; cout<<"\n"; // Take the input of the array. for(j = 0; j < n; j++) { cout<<"Enter "<<j+1<<" element: "; cin>>arr[j]; } // Print the subset using binary counting method. cout<<"\nThe possible subset pairs which on union generates the superset, are: \n"; GenUnionSet(arr, n); return 0; }