CareerCup

This is a standard implementation of backtracking algorithm.

The enumeration for the 5 example is wrong.

A sequence of positive integers summing to an integer n is called a composition of n. If you think of n as 1 + 1 + ... + 1, a composition corresponds to replacing some of the plus signs with commas. There are n terms and hence n-1 plus signs, so there are C(n-1, k) compositions of n with k parts. Summing over all k gives C(n-1, 0) + C(n-1, 1) + C(n-1, 2) + ... + C(n-1, n-1) = 2^(n-1). Discounting the 1-term composition that consists of just n itself, that leaves 2^(n-1) - 1 compositions. Your 4 example has 7 = 2^(4-1) - 1 objects, so it checks out. But your 5 example has only 12 objects, whereas the formula says it should have 2^(5-1) -1 = 15.

This counting argument shows that brute-force enumeration without dynamic programming is the best you can do if you want to represent all the compositions explicitly. Here's a program that enumerates all compositions of an integer:

#include <stdio.h>

void printa(int *a, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

void compositions(int *a, int n, int k)
{
    if (n == 0) {
        printa(a, k);
        return;
    }
    for (int p = 1; p <= n; p++) {
        a[k] = p;
        compositions(a, n-p, k+1);
    }
}

int main()
{
    int a[10];
    compositions(a, 5, 0);
    return 0;
}

Running this shows that the compositions of 5 missing from your example are 1 2 2, 2 1 2 and 2 2 1.