C++ Programming Code Examples C++ > Sorting Searching Code Examples Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself - This algorithm counts the partition of the given number. - There is no straight method to count a total number of the partition so we need to generate and count them. - The time complexity of this algorithm is O(n!). - This algorithm takes the input of a number 'n'. - It starts with the number and breaks it by removing 1, at a time.. - As it generates a new partition increase the counter. - Print the result. - Exit. #include<iostream> using namespace std; // A function to count all the possible partition. int CountPartitions(int n) { int p[n], k = 0, count = -1; p[k] = n; // Loop until all the array elements converted to 1 mean no further partition can be generated. while(1) { count++; 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 count; // 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, c; cout<<"Enter natural numbers for partition counting: "; cin>>n; if (n <= 0) { cout<<"Wrong input!!"; return 0; } c = CountPartitions(n); cout<<"The number of partitions of with each element lesser than "<<n<<" is:- "<<c; return 0; }