subset sum problem

Algorithm #8: Dynamic Programming for Subset Sum problem

Uptil now I have posted about two methods that can be used to solve the subset sum problem, Bitmasking and Backtracking. Bitmasking was a brute force approach and backtracking was a somewhat improved brute force approach.

In some cases, we can solve the subset sum problem using Dynamic Programming. (Note that I said “in some cases”). This post is an introduction to Dynamic programming.

Okay, so first questions first… What is Dynamic Programming?
Dynamic programming is not an algorithm in itself, it is a programming strategy. The basic idea behind DP is that while computing for the answer, we store the results of the intermediate computations so that we don’t need to recompute them later. We first compute the answer of smaller versions of our problem and store the answers. These intermediate answers help us compute the actual answer and as they are already stored somewhere we don’t need to recalculate them everytime we need them. This saves up a lot of time. That’s DP in a nutshell. There is much more to the definition of Dynamic Programming that you can read on Wikipedia. But for now, this simple definition will do.
This discussion on quora might help.

Let’s look at Subset Sum problem again:

We are given a set of N numbers. Our objective is to find out if it is possible to select some numbers from this set such that their sum exactly equals M. Eg. If we have the numbers {3,5,3,1} and M=8, then the answer is “yes” because of the subset {3,5}. If M=10, then the answer is “no” because no subset has sum=10.

The DP solution looks like this:

#include
int main()
{
    int N,M;
    scanf(" %d %d",&N,&M);
    int nums[N+1],i,j,ispossible[N+1][M+1];
    for(i=1;i<=N;i++)
        scanf(" %d",&nums[i]);
    for(i=0;i<=N;i++)
        for(j=0;j<=M;j++)
            ispossible[i][j]=0;//initialising to 0
    for(i=0;i<=N;i++)
        ispossible[i][0]=1;
    for(i=1;i<=N;i++)
    {
        for(j=0;j<=M;j++) { if(ispossible[i-1][j]==1) ispossible[i][j]=1; if(j-nums[i]>=0 && ispossible[i-1][j-nums[i]]==1)
                ispossible[i][j]=1;
        }
    }
    if(ispossible[N][M]==1)
        printf("Yes");
    else
        printf("No");
    return 0;
}

I’ve taken the input in nums[1], nums[2], … , nums[n]
I’ve used a 2-D array named ispossible[ ][ ]. It has size(N+1) x (M+1).
ispossible[i][j] can be either 0 or 1. Its value will be 1 if it is possible to select some numbers from the set {nums[1],nums[2],nums[3],…,nums[i]} so that their sum equals to j; otherwise it will be 0.

The logic is really simple:

Our final goal is to find the value of ispossible[N][M], which will be 1 if it is possible to obtain a subset of {nums[1],nums[2],nums[3],…,nums[N]} with sum equal to M.
To find the value of ispossible[N][M] we need to find the value of each element in the two dimensional array ispossible[ ][ ].

In general, ispossible[i][j] = 1 iff one of the following two conditions is true:

1. ispossible[i-1][j] is 1. If ispossible[i-1][j] is 1 it means that it is possible to obtain a sum of j by selecting some numbers from {nums[1],nums[2],nums[3],…,nums[i-1]}, so obviously the same is also possible with the set {nums[1],nums[2],nums[3],….,nums[i-1],nums[i]}.

2. ispossible[i-1][j-nums[i]] is 1. If ispossible[i-1][j-nums[i]] is 1 it means that it is possible to obtain a sum of (jnums[i]) by selecting numbers from {nums[1], nums[2],…,nums[i-1]}. Now if we select nums[i] too, then we can obtain a sum of (jnums[i])+nums[i] = j. Therefore ispossible[i][j] is 1.

The above two points serve as the DP equation for calculating all values in ispossible[ ][ ].

Note that first it is important to set ispossible[i][0] = 1 (for 0<=i<=N). Because obviously its possible to obtain a sum = 0 from any value of i.
This algorithm has time complexity O(N*M) and space complexity O(N*M).
The drawback of this algorithm and the reason why I said “in some cases” before is that if N*M is too large, then an array of the required size cannot be declared. So, this method works well only in those cases where N*M is around 10^8.

As I said earlier, Dynamic Programming is not a single algorithm but it is a programming strategy. A programming strategy that can be mastered only by practice. Dynamic programming questions are always unique and new. Each question has its own equation. By practicing enough DP questions you’ll learn how to recognize DP questions and how to think of their equation and solution.

RELATED PROBLEM:
Paying up ( Codechef ): This is a really simple DP problem that is exactly as the problem described in this post.
Fence ( Codeforces )
More questions can be found on Codeforces here.

Advertisements

Algorithm #6: Backtracking

I think we are ready to discuss Backtracking now. Last time I posted about recursion; I hope it’ll help you with this topic.
When I told you about Bit Masking, I said that it is a brute force approach to solve the Subset Sum problem. And better algorithms than Bit Masking exist. Backtracking is one of those methods.

In my post about Bitmasking I discussed the Subset Sum problem. Subset sum problem is an NP complete problem. In a nutshell, NP complete is a set of computational problems for which no efficient solution that will give a reasonably good run time for very large test cases has yet been found. The complexity of Bitmasking is O(2^n) and it becomes useless at n>25 due to the dramatic increase in the number of subsets that need to be analysed.

In subset sum problem, we are given a set of positive numbers. We are asked if it is possible to find a subset of this set such that the sum of numbers of the selected subset is exactly m ( a positive number).
Backtracking can be viewed as an attempt to improve the Bitmasking algorithm. Just to remind you, in Bitmasking we analyse all the possible subsets of the given set to find a possible solution subset.
But in backtracking, we will intelligently reject the subsets that we know for sure will not lead to a solution.

For example, suppose we have n=5 and the set is {5,31,3,7,6}. We have to select a subset such that the sum of numbers of the selected subset is 11. Now it is obvious that no subset containing the number 31 can have a sum of 11. So, no subset involving the number 31 will lead to a solution. So, we should not consider those subsets that have 31 in them. We should not waste our time analyzing those subsets. This is the principle of Backtracking. As soon as we come to know that selecting 31 will not lead to a solution, we do not continue analysing subsets with 31 in them.

Below is the code to solve the subset sum problem using backtracking:
backtrack() is a function that takes the set of numbers ( nums[ ] ), the total number of elements ( n ), and the sum that we require ( requiredsum ).
It returns 1 if it is possible to obtain a sum of exactly requiredsum, and 0 if it is not possible to do so.

int backtrack(int nums[],int at,int n,int sumrequired)
{
    if(sumrequired==0)
        return 1;
    if(sumrequired<0)
        return 0;
    if(at==n)
        return 0;
    if(backtrack(nums,at+1,n,sumrequired-nums[at])==1)
        return 1;
    if(backtrack(nums,at+1,n,sumrequired)==1)
        return 1;
    return 0;
}

I mentioned in my post about recursion that programs implemented using recursion can be incredibly short and incredibly difficult to understand. This is an example of that!

Following are the important points about this algorithm:

1. The at variable tells which number’s fate we are deciding. If in a recursive instance at is i, it means that we are currently deciding the fate of the ith number.
2. If the sumrequired variable is 0, it means that we do not need to select any more numbers, so we return the success code (which is 1).
3. A negative sum of numbers can never be achieved because all numbers can have only positive values; so if sumrequired is negative, we return the failure code (which is 0).
4. The recursive call at line 9 represents the case where we select the current number ( nums[at] ). When we select the current number, our problem reduces to selecting numbers from the set {nums[at+1], nums[at+2],…, nums[n-1]} such that their sum is (requiredsum – value[at]) .
5. The recursive call at line 11 represents the case where we don’t select the current number ( nums[at] ). If we don’t select the current number, our problem reduces to selecting numbers from the set {nums[at+1], nums[at+2],…, nums[n-1]} such that their sum is requiredsum itself.

I defined in my previous post that recursion is when we decompose a problem into a smaller problem.
See points 4 and 5 carefully. I am reducing my current problem of finding a solution subset from the set {nums[at],nums[at+1],nums[at+2],…,nums[n-1]} to finding a solution subset from the set {nums[at+1], nums[at+2],…, nums[n-1]}.
Whenever I find a solution (i.e. when requiredsum =0), all recursive calls will terminate one by one and 1 will be returned at each level.

At any time if requiredsum becomes less than 0, it means that the numbers that we have selected till now have their sum greater than the initial requiredsum already . So there’s no point in going furthur. Therefore, we return 0; which denotes that the current choices of elements will not lead to any solution.

In the test case I discussed before (with n=5 and the set of numbers as {5,31,3,7,6} and requiredsum=11),
if we select the number 31, the value of requiredsum will become < 0 in the next recursive call. And that recursive instance will immediately return 0; ( see point 2 )it will not go on deciding the fate of the rest of the numbers. In this way we simply discarded the subsets including the number 31.

The worst case complexity of this algorithm is same as Bitmasking i.e. O(2^n). But it offers a better execution time as it deliberately and intelligently skips some subsets.

PROBLEMS:
PAYING UP (on Codechef)

As it is with all recursive solutions, the code may seem overwhelming at first. I suggest that you look at the order of recursive calls I showed in the last post ( here ) and try to trace the way recursive calls are made in this case.

Algorithm #4: Bit Masking

First of all, I’d like to apologize for not having posted anything at all since so many weeks. I’ll try to be fairly regular from now.

The topic that I am going to discuss now is called Bit Masking. This technique is useful when you have a set and have to select a subset from it that satisfies a particular condition.  The following would be a nice example. It is called the ‘Subset Sum Problem’.

You have n coins with you; each coin has a particular value. You want to select some coins such that the sum of value of the selected coins is m.

So, each coin can have one of two fates: either it is selected or it is not. Lets solve this problem for n=4, m=10 and the value of coins as 2,3,5,7. There are a total of 2^4=16 subsets possible. In other words, there are 16 ways of selecting coins.

Let me draw your attention to an interesting fact. When you count from 0 to 15 in binary, you obtain all the possible length 4 permutations of 0s and 1s. We shall use this fact to generate all the subsets of {2,3,5,7}. Each of the numbers from 0 to 15 will represent a different subset of the set {2,3,5,7}. For instance, the number 14 (1110 in binary) represents the subset {2,3,5}, the number 10 (or 1010 in binary) represents the subset {2,5}, and 15 (1111 in binary) represents {2,3,5,7} and 0 (or 0000 ) represents {}. So, if the ith bit in the binary representation is 1, then the ith number in the set is selected otherwise it is rejected.

Just for clarity, I’m listing below the subset that each number represents:

Initial set= {2,3,5,7}

Number Its Binary Subset it represents
0 0000 {}
1 0001 {7}
2 0010 {5}
3 0011 {5,7}
4 0100 {3}
5 0101 {3,7}
6 0110 {3,5}
7 0111 {3,5,7}
8 1000 {2}
9 1001 {2,7}
10 1010 {2,5}
11 1011 {2,5,7}
12 1100 {2,3}
13 1101 {2,3,7}
14 1110 {2,3,5}
15 1111 {2,3,5,7}

So, to find the answer for the initial problem, all we have to do is iterate a variable (say, i) from 0 to 15; during each iteration find the subset that i represents and then check if it satisfies the condition.

The code will look something like

#include<stdio.h>
int main()
{
    int n,coins[10000],j;
    long long m;
    scanf(" %d %lld",&n,&m);
    long long last=(1<<n)-1; // generalizing, we have iterate from 0 to 2^n - 1
    long long i,temp,currentsum;
    i=0;
    while(i<n)
    {
        scanf(" %d",&coins[i]);
        i++;
    }
    for(i=0;i<=last;i++)
    {
        temp=i; //stored i in a different variable to save it from modification
        currentsum=0; // to keep track of the sum of values of selected coins
        j=0;
        /*-----SUBSET GENERATION PROCESS START-----*/
        printf("Checking subset : { ");
        while(j<n) // for each bit of temp
        {
            if(temp%2==1) //examining the last bit (LSB) of temp. If it is 1, we take the coin
            {
                printf("%d ",coins[j]);
                currentsum+=(coins[j]);
            }
            temp>>=1; //right shifting temp, so that we may analyze the next least significant bit in the next iteration of while loop
            j++;
        }
        /*-----SUBSET GENERATION PROCESS OVER-----*/
        printf("} Sum= %lld",currentsum);
        /*-----CONDITION EVALUATION FOR THE CURRENT SUBSET-----*/
        if(currentsum==m)
        {
            printf("Found solution subset");
            //break;
        }
        /*-----CONDITION EVALUATION OVER-----*/
        printf("\n");
    }
    return 0;
}

The body of the outer ‘for’ loop can be changed in accordance to what the problem is. In this case, we just needed the sum of numbers of each subset, so I did a running total of the value of coins selected. And when we obtain the sum of that subset, we check if it is equal to m. I’ve added printfs in the code at various places to make things clearer. Try it out by running it on your machine.

There is an obvious drawback to this method. As we are examining all possible subsets, this is a brute-force approach. If n becomes greater than 25 this method will be very slow. And, of course, we also have the limitation that we cannot have an integer larger than 64 bits in C/C++, so this method will not work for n greater than 64 ( though, as mentioned earlier, the method already becomes impractical at around n=25) .

There exists no efficient algorithm for Subset Sum problem. We may optimize our algorithm in many different ways, but a perfect solution has not yet been discovered. All algorithms that exist currently will become slower and, therefore, inefficient very quickly as n increases. Bit Masking is one of the many solutions that exist currently. There are many other, more efficient solutions (comparatively more efficient) that are quite complex to be discussed currently.

In a nutshell, this method is very easy to code and is very good for programming competitions if n is small enough. There is an alternate method very popular in competitive programming called ‘Backtracking’ which I’ll discuss in future.

If you want to practice bit masking then follow these links:

http://www.codechef.com/problems/MARCHA1 (Simple)

http://www.codechef.com/problems/LEALCO (Medium difficulty)

NOTE:
1. For those who are comfortable with the notation of complexity, the computational complexity of this algorithm is O(n*2^n)
2. Lines 26 and 27 in the code may just as well been

printf("%d ",coins[n-j-1]);
currentsum+=(coins[n-j-1]);

because it doesn’t matter if you start counting the bits from the left or from the right