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:

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

advertisement
advertisement

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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.