Question

How to find all possible ways to write a positive integer as a sum of positive integers in C

Answer 1

#include <stdio.h>

// Print a partition stored in 'arr' in the form "a + b + c"
void print_vector(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (i > 0) printf(" + ");   // add plus signs between numbers
        printf("%d", arr[i]);
    }
    printf("\n");
}

/*
    Generate all partitions of a number using non-decreasing sequences.

    arr       – current partial partition being built
    size      – how many elements are currently in arr
    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    remaining – how much is left to reach the target sum

    When remaining == 0, arr contains a complete valid partition.
*/
void partitions(int arr[], int size, int start, int remaining) {
    // Base case: exact sum reached
    if (remaining == 0) {
        if (size >= 2)      // enforce "two or more integers"
            print_vector(arr, size);
        return;
    }

    // Try all next values from 'start' up to 'remaining'
    for (int j = start; j <= remaining; j++) {
        arr[size] = j;                          // choose j
        partitions(arr, size + 1, j, remaining - j);  // recurse with reduced remainder
        // no need to "pop" in C; we just overwrite next time
    }
}

int main() {
    int n = 5;                 // number to partition
    int arr[128];              // holds current partition (large enough buffer)

    partitions(arr, 0, 1, n);  // start with smallest allowed value = 1
    
    return 0;
}



/*
run:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>

/*
    Generate all ways to write a positive integer n
    as a sum of positive integers (integer partitions).

    Example for n = 5:
    [
      [ 5 ],
      [ 4, 1 ],
      [ 3, 2 ],
      [ 3, 1, 1 ],
      [ 2, 2, 1 ],
      [ 2, 1, 1, 1 ],
      [ 1, 1, 1, 1, 1 ]
    ]
*/

/*
    Backtracking helper function.

    remaining - how much is left to reach n
    maxValue  - maximum allowed next number (keeps order non-increasing)
    current[] - current partial partition
    index     - current length of the partition
*/
void backtrack(int remaining, int maxValue, int current[], int index) {
    // If nothing remains, we found a valid partition
    if (remaining == 0) {
        printf("  [ ");
        for (int i = 0; i < index; i++) {
            printf("%d", current[i]);
            if (i < index - 1)
                printf(", ");
        }
        printf(" ]\n");
        return;
    }

    // Try next numbers from maxValue down to 1
    for (int next = (remaining < maxValue ? remaining : maxValue); next >= 1; next--) {
        current[index] = next; // choose
        backtrack(remaining - next, next, current, index + 1); // explore
    }
}

/*
    Function that prints all partitions of n
*/
void partitions(int n) {
    int current[100]; // enough for any reasonable partition
    backtrack(n, n, current, 0);
}

int main() {
    printf("[\n");
    partitions(5);
    printf("]\n");

    return 0;
}



/*
run:

[
  [ 5 ]
  [ 4, 1 ]
  [ 3, 2 ]
  [ 3, 1, 1 ]
  [ 2, 2, 1 ]
  [ 2, 1, 1, 1 ]
  [ 1, 1, 1, 1, 1 ]
]

*/

 

70+ SQL courses for beginners and professionals