Subset Sums

I had gotten $5983373858461353469$ from using an array int64 variables instead of BigInteger variables to store intermediate solutions. I had also requested that this problem be tagged under #ComputerScience instead.

Since checking through all $2^{100}$ subsets would take an impossibly long time (even for a standard computer), a faster approach is needed. The one which I came up with is inspired by generating functions. More specifically, the number of subsets which sum to $1000$ is given by the coefficient of $x^{1000}$ in the product $\prod\limits_{i = 1}^{100} (1 + x^{i})$ . I will not explain this here, but this is the basis for the solution shown here.

For every element $k$ in the set of integers from $1$ to $100$ inclusive, $k$ is either included in a subset, or it is not. Therefore, if there is already a running list of the number of subsets which sum to a particular value, it is possible to add on the subsets which include $k$ to the running list. For example:

Starting:

Subsets with sum $0$ : $1$

$k = 1$ :

Subsets with sum $0$ : $1$

Subsets with sum $1$ : $0 + 1 = 1$

$k = 2$ :

Subsets with sum $0$ : $1$

Subsets with sum $1$ : $1$

Subsets with sum $2$ : $0 + 1 = 1$

Subsets with sum $3$ : $0 + 1 = 1$

$k = 3$ :

Subsets with sum $0$ : $1$

Subsets with sum $1$ : $1$

Subsets with sum $2$ : $1$

Subsets with sum $3$ : $1 + 1 = 2$

Subsets with sum $4$ : $0 + 1 = 1$

Subsets with sum $5$ : $0 + 1 = 1$

Subsets with sum $6$ : $0 + 1 = 1$

$k = 4$ :

Subsets with sum $0$ : $1$

Subsets with sum $1$ : $1$

Subsets with sum $2$ : $1$

Subsets with sum $3$ : $2$

Subsets with sum $4$ : $1 + 1 = 2$

Subsets with sum $5$ : $1 + 1 = 2$

Subsets with sum $6$ : $1 + 1 = 2$

Subsets with sum $7$ : $0 + 2 = 2$

Subsets with sum $8$ : $0 + 1 = 1$

Subsets with sum $9$ : $0 + 1 = 1$

Subsets with sum $10$ : $0 + 1 = 1$

Continuing the pattern up to $100$ gives that the number of subsets is $633172672364586108413$ $$ . Another possible optimization is only storing the values mod $1000$ , since not only the answer will be in a more convenient form, but if using a language like C++ or Java, 16 or 32 bit integers will suffice instead of the otherwise required BigIntegers.

Here is a snippet of code from my Java solution:

N = 100;

K = 1000;

arr = new BigInteger[K + 1];

Arrays.fill(arr, BigInteger.ZERO);

arr[0] = BigInteger.ONE;

for(int i = 1; i < N + 1; i++) {

    for(int j = K - i; j > -1; j--) {

        arr[j + i] = arr[j + i].add(arr[j]);

    }

}

System.out.println(arr[1000].toString());

I wrote a simple C++ program to recursively compute the number of subsets knowing the last integer taken and the sum of all integers in the subset I'm matching.

To speed up the algorithm we can see that there are some sub-problems that we have to compute more than once: it's time to DP! We just have to save our results into a matrix and return them when necessary.

Time complexity O( N^3 ) where N is the number of starting elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <string.h>
using namespace std;

int mem[105][100*101/2 +1];

int subset(int last, int sum)
{
        if( mem[last][sum]!=-1 ) return mem[last][sum];
        if(sum>1000) return mem[last][sum]=0;
        if(sum==1000) return mem[last][sum]=1;
        int numb=0;
        for(int i=last+1; i<=100; i++) numb+=subset(i,sum+i);

        return mem[last][sum]=numb%1000;
}

int main()
{
        int numb=0;
        memset( mem, -1, sizeof(mem) );

        for(int i=1; i<=100; i++) numb+=subset(i,i);

        cout << numb%1000 << endl;

    return 0;
}

Have a look at this

Replace the first two lines with:

Numbers=xrange(1,101)
Maximum=1000

And run the code!

There is a complete explanation in Stackoverflow