Subset Sum Problem

subset sum problem

---------------------

A subset sum problem is a NP-complete problem. For more information visit http://en.wikipedia.org/wiki/Subset_sum_problem

However if we have knowledge about the data, we can use various optimizations such that the problem can be solved in polynomial time.

One such technique is presented below.

Given an array, we wish to count how many ways we can get a particular sum.

Let an array A[]= { a1, a2, ...an }. How many ways can we get a particular sum S.

also 0<=ai<=MAX.

Here i will describe a O(n*MAX) algorithm to solve it.

int T[MAX]; //T[i] stores how many ways we can get a sum = i.

int subset_sum(int A[] , int n, int S)
{
    int prev_max=0;
    T[0]=1; //we can get a sum of 0 in 1 way.
    for( int i=0; i < n; i++ )
    {
        for(int j = prev_max ; j >= 0; j--)
            if (T[j])
            {
                T[j+A[i]] += T[j];
                prev_max = max( prev_max , j+A[i] );
            }
    }
    return T[S]; 
}

Pretty simple. isn't it? :)

There are some things to note here.

Why do we run the second for loop from back?

->if we ran the loop from the front (ie from j to prev_max) then following thing will happen.

suppose for some value of j we have T[j]=non-zero number. thus we update at T[j+A[i]].

later when j becomes j+A[i], T[j+A[i]] is again non-zero from previous update. thus we update at T[j+A[i]+A[i]].

ie. we will end up using the same number A[i] more than once. this is not allowed.

How large can MAX or n be?

-> That depends on 2 things. How much memory can you allocate? and What is the speed of your system?

Standard Online judge like SPOJ, Codechef are pretty slow and allow memory allocation up to 10^8 bytes.

They run a plain for loop of 10^8 in a little more than 1 second.

So for the problem to be solved using this algorithm n*MAX ~ 10^8 or less.

Do let me know if you have any questions.