C Program to Perform Integer Partition for a Specific Case

This C program perform integer partition for a specific case.

This algorithm partitions an integer into numbers which sum up to form the original number.

Here is the source code of the C program to perform integer partition. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
typedef struct {
```
```
     int first;
```
```
     int n;
```
```
     int level;
```
```
} Call;
```
```
 
```
```
 
```
```
void print(int n, int * a) {
```
```
     int i ;
```
```
     for (i = 0; i <= n; i++) {
```
```
          printf("%d", a[i]);
```
```
     }
```
```
     printf("\n");
```
```
}
```
```
 
```
```
 
```
```
void integerPartition(int n, int * a){
```
```
     int first;
```
```
     int i;
```
```
     int top = 0;
```
```
     int level = 0;
```

     Call * stack = (Call * ) malloc (sizeof(Call) * 1000);

```
     stack[0].first = -1;
```
```
     stack[0].n = n;
```
```
     stack[0].level = level;
```
```
     while (top >= 0){
```
```
          first = stack[top].first;
```
```
          n = stack[top].n;
```
```
          level = stack[top].level;
```
```
          if (n >= 1) {
```
```
               if (first == - 1) {
```
```
                    a[level] = n;
```
```
                    print(level, a);
```

                    first = (level == 0) ? 1 : a[level-1];

```
                    i = first;
```
```
               } else {
```
```
                    i = first;
```
```
                    i++;
```
```
               }
```
```
               if (i <= n / 2) {
```
```
                    a[level] = i;
```

                    stack[top].first = i;

```
                    top++;
```

                    stack[top].first = -1;

                    stack[top].n = n - i;

                    stack[top].level = level + 1;

```
          } else {
```
```
               top--;
```
```
          }
```
```
     } else {
```
```
     top --;
```
```
     }
```
```
}
```
```
}
```
```
 
```
```
int main(){
```
```
    int n = 4;
```

    int * a = (int * ) malloc(sizeof(int) * n);

    printf("\nThe integer partition for %d is :\n", n);

```
    integerPartition (n, a);
```
```
    return(0);
```
```
}
```

$ gcc integer_partition.c -o integer_partition
$ ./integer_partition
The integer partition for 4 is :
4
13
112
1111
22

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 the Set Partitions of n Numbers Beginning from 1 and so on

» Next - Solving Linear Equations in One Variable Using C

Related Posts:

Recommended Articles: