# C Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself

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.

1. #include<stdio.h>
2. #include<math.h>
3. #include<time.h>
4. #include<stdlib.h>
5.
6. void printArray(int p[], int n) {
7.     int i;
8.     for (i = 0; i < n; i++)
9.         printf("%d ", p[i]);
10.     printf("\n");
11. }
12.
13. void printAllUniqueParts(int n) {
14.     int p[n]; // An array to store a partition
15.     int k = 0; // Index of last element in a partition
16.     p[k] = n; // Initialize first partition as number itself
17.     while (1) {
18.         printArray(p, k + 1);
19.         int rem_val = 0;
20.         while (k >= 0 && p[k] == 1) {
21.             rem_val += p[k];
22.             k--;
23.         }
24.
25.         if (k < 0)
26.             return;
27.         p[k]--;
28.         rem_val++;
29.         while (rem_val > p[k]) {
30.             p[k + 1] = p[k];
31.             rem_val = rem_val - p[k];
32.             k++;
33.         }
34.         p[k + 1] = rem_val;
35.         k++;
36.     }
37. }
38.
39. int main() {
40.     printf("All Unique Partitions of 2 \n");
41.     printAllUniqueParts(2);
42.
43.     printf("\nAll Unique Partitions of 3 \n");
44.     printAllUniqueParts(3);
45.
46.     printf("\nAll Unique Partitions of 4 \n");
47.     printAllUniqueParts(4);
48.
49.     return 0;
50. }

Output:

\$ ./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.