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.

```
#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 Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Generate All Possible Subsets using Gray Code Order

» Next - C Program to Find the Mode of a Data Set

Related Posts:

Check C Books
Practice Computer Science MCQs
Apply for C Internship
Practice BCA MCQs
Check Computer Science Books

Recommended Articles: