This is a C Program to find the number of ways to write a number as the sum of numbers smaller than itself. We print all partition in sorted order and numbers within a partition are also printed in sorted order (as shown in the above examples). The idea is to get next partition using the values in current partition. We store every partition in an array p[]. We initialize p[] as n where n is the input number. In every iteration. we first print p[] and then update p[] to store the next partition. So the main problem is to get next partition from a given partition.

Here is source code of the C Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself . The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include<stdio.h>`

`#include<math.h>`

`#include<time.h>`

`#include<stdlib.h>`

void printArray(int p[], int n) {

int i;

for (i = 0; i < n; i++)

printf("%d ", p[i]);

printf("\n");

`}`

void printAllUniqueParts(int n) {

int p[n]; // An array to store a partition

int k = 0; // Index of last element in a partition

p[k] = n; // Initialize first partition as number itself

while (1) {

printArray(p, k + 1);

int rem_val = 0;

while (k >= 0 && p[k] == 1) {

rem_val += p[k];

`k--;`

`}`

if (k < 0)

return;

p[k]--;

`rem_val++;`

while (rem_val > p[k]) {

p[k + 1] = p[k];

rem_val = rem_val - p[k];

`k++;`

`}`

p[k + 1] = rem_val;

`k++;`

`}`

`}`

int main() {

printf("All Unique Partitions of 2 \n");

printAllUniqueParts(2);

printf("\nAll Unique Partitions of 3 \n");

printAllUniqueParts(3);

printf("\nAll Unique Partitions of 4 \n");

printAllUniqueParts(4);

return 0;

`}`

Output:

$ gcc SumOfNumbersSmallerThanItself.c $ ./a.out All Unique Partitions of 2 2 1 1 All Unique Partitions of 3 3 2 1 1 1 1 All Unique Partitions of 4 4 3 1 2 2 2 1 1 1 1 1 1

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.