C++ Programming Code Examples C++ > Beginners Lab Assignments Code Examples Program to Generate All Subsets of a Given Set in the Gray Code Order Program to Generate All Subsets of a Given Set in the Gray Code Order - This algorithm print all the possible combination of each length from the given array in gray code order. - The time complexity of this algorithm is O(n*(2^n)). - This algorithm takes the input of 'n' data element and prints all possible combination. - For that, it generates the gray code and prints the corresponding array element of the array. - Exit. #include <iostream> #include <math.h> using namespace std; // A function to print array element according to the code in the argument list. void print(int code[], int arr[], int n) { int i; cout<<"\t{ "; for(i = 0; i < n; i++) { // Print if the corresponding value is true. if(code[i] == 1) cout<<arr[i]<<" "; } cout<<"}\n"; } // A function generating gray codes. void GenGrayCode(int arr[], int n) { int r, i, k, j, l, code[n], a[n]; r = pow(2,n); // External loop to generate 2^n subsets. for(i = 0; i < r; i++) { k=i; // Loop to store the i value in binary in the a[] array. for(j = n-1; j >= 0; j--, k /= 2) a[j] = k%2; k = 0 ; l = 0; // From the binary value generate the corresponding gray code. for(j = 0; j < n; j++) { // If the first value is 1 then assign it into the gray code array if(k == 0) { if(a[j] == 1) k++; code[l] = a[j]; l++; } // If the current bit in the binary code is equal to the previous value then assign the corresponding gray code value to 0. else if(a[j] == a[j-1]) { code[l] = 0; l++; } // Otherwise assign the corresponding gray code value to 1. else { code[l] = 1; l++; } } // As the next code generated, call print(). print(code , arr, n); } } int main() { int i, n; cout<<"\nEnter the number of element array have: "; cin>>n; int arr[n]; cout<<"\n"; // Take the input of the array. for(i = 0; i < n; i++) { cout<<"Enter "<<i+1<<" element: "; cin>>arr[i]; } // Print the subset in the gray code order. cout<<"\nThe subset in the gray code order: \n"; GenGrayCode(arr, n); return 0; }