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 (j–nums[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 (j–nums[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.