C++ Programming Code Examples C++ > Sorting Searching Code Examples Generate All the Set Partitions of n Numbers Beginning from 1 and so on Generate All the Set Partitions of n Numbers Beginning from 1 and so on - This algorithm generates all the possible partition can be generated by breaking the given integer value. - The time complexity of this algorithm is O(n*n!). - This algorithm takes the input of a natural number and prints all the possible partition of each number less than or equal to it. - For each number, it starts with the number and breaks it by 1, at a time. - Exit. #include<iostream> using namespace std; // A function to print the generated partition. void printArray(int p[], int n) { cout<<"\t"; for (int i = 0; i < n; i++) cout<<p[i]<<" "; cout<<"\n"; } // A function to print all the possible partition. void PrintAllUniqueParts(int n) { int p[n], k = 0; p[k] = n; // Loop until all the array elements converted to 1 mean no further partition can be generated. while(1) { printArray(p, k + 1); int rem_val = 0; // Move the pointer to the index so that p[k] > 1. while (k >= 0 && p[k] == 1) { rem_val += p[k]; k--; } // If k < 0 then the all the element are broken down to 1. if (k < 0) return; // If value greater than 1 is found then decrease it by 1 and increase rem_val to add it to other elements. p[k]--; rem_val++; // Loop until the number of 1's are greater than the value at k index. while (rem_val > p[k]) { p[k+1] = p[k]; // Decrease the rem_val value. rem_val = rem_val - p[k]; k++; } // Assign the remaining value to the index next to k. p[k+1] = rem_val; k++; } } int main() { int n; cout<<"Enter natural numbers for creating partitions: "; cin>>n; if (value <= 0) { cout<<"Wrong input!!"; break; } cout<<"All Unique Partitions of "<<n<<" are:-\n"; PrintAllUniqueParts(n); return 0; }