Subset sum problem.

Problem Statement: Given a set of numbers A[1...n], find a subset which sums up to a given number S.

Solution #1: Below is the code using Brute-force approach. The complexity is O(2^n).

int subsetSum(int* A, int len, int sum)
{
    if(sum == 0)
        return 1;
    
    if((len < 0) || (sum < 0))
        return 0;

    return subsetSum(A+1, len-1, sum) || subsetSum(A+1, len-1, sum-A[0]);
}

Solution #2: A faster way to solve this problem is by using dynamic programming. Below is the equation and the code,

RES[i][j] : is '1' if there is a subset in set A[1...i] which sums up to 'j', '0' otherwise.

RES[i][j] = RES[i-1][j] | RES[i-1][j-A[i]]

int RES[100][100];

int subsetSumDyn(int* A, int len, int sum)
{
    int i,j;

    for(j=0; j<=sum; j++)
        RES[0][j] = 0;
    
    for(i=0; i<=len; i++)
        RES[i][0] = 1;

    for(i=1; i<=len; i++)
    {
        for(j=1; j<=sum; j++)
        {
            int index = j - A[i-1];
            if(index >=0)
                RES[i][j] = RES[i-1][j] | RES[i-1][index];
            else
                RES[i][j] = RES[i-1][j];
        }
    }

    return RES[len][sum];
}

int main()
{
    int A[] = {13, 21, 11, 14, 4, 5};
    int len = sizeof(A)/sizeof(int);

    printf("Subset sub: %d\n", subsetSumDyn(A, len, 32));
    return 0;
}