Dynamic Programming: Subset Sum Problem
Dynamic Programming Problem #2 : Subset Sum
Before starting up with the Subset Sum Problem, I would highly recommend you to read this introduction to Dynamic Programming. Here I have covered the basic method on how to approach a DP based problem. We will be using the same concepts to solve the Subset Sum problem. I’d also recommend to go through the Knapsack Problem since it’s the parent problem for Subset Sum Problem.
With that being said, let’s begin!
1. What is Subset Sum Problem ?
Given a set of N non-negative integers and a target sum S, determine if there exists a subset of the given set such that the sum of the elements of the subset equals to S. Return 1 if there exists such subset, otherwise return 0.
2. Recursion, Memoization & Tabulation
This problem is very similar to the 0–1 Knapsack Problem, which in this case is it’s parent problem. Thus I recommend you to have a look at the same.
If you’d have read the two, above mentioned articles, then you would know that in order to write a proper DP based solution one must be able to think of a recursive solution. We will be using Python3 for coding the solutions for this problem. So let’s see what a Recursive solution would be like.
a) Recursive Approach
In order to write a recursive solution, one must be able to figure out two things : Base Condition & Recursion Logic/Recurrence Relation.
- Base Condition : The base condition always refers to the smallest possible case(s) for the problem we are trying to solve. In this case there are two possibilities :
- If target sum S is equal to 0. In this case no matter what the given set is, one would always be able to find a subset (which is null set) such that some of the elements of that subset is 0.
- If the number of elements in the set (N) is zero. In this case no matter how hard you we try, we won’t be able to get a subset such that the sum of elements is equal to target sum S. Thus in all these cases we return False. However if N = 0 as well as S = 0, we return True since the null set satisfies the requirements. But since we have already covered this case in last point, we need not worry about it here.
2. Recursion Logic : Just like we did in 0–1 Knapsack Problem, even here we see if there is a possibility of including the number in the subset or not.
- The value of the number must be less than or equal to the target sum B for it to be considered for inclusion.
- If the number can be included, we consider two cases :
- Inclusion of number : If the number is included then we reduce the target sum by the number and continue to next recursive call.
target_sum = target_sum - number2. Exclusion of number : If the number is not included then the target sum remains unchanged and we simply proceed to the next recursive call.
With all this in mind, this is how a recursive solution would look like
With the basic logic and consideration of cases we discussed earlier, above is the proper recursive implementation of the same. Now that we have the recursive solution let’s convert this into a memoized solution.
b) Memoization
From our discussions in this and this, we all know that we must keep following points in mind while writing a memoized solution :
- In order to reduce the recursive calls, we save the computed values for later use. I prefer to call this variable store.
- The dimensions of store depends on the number of changing parameters in our recursive solution. Which in this case is 2 : target sum & N. Since target sum can take a total of S+1 and number of elements can take a total of N+1 possible values. Thus we have store[N+1][S+1].
- Before computing the answer for any call we check for the presence of answer in store. If it is present, we return the same. Otherwise we compute it and store it for later use.
- The easiest way to visualize store is to understand the fact that (in this case)in general store[n][s] holds the answer for the function call isSubsetSum(number_set, n, s).
With these points in mind, let’s see how a modified solution would look like.
That’s how we would memoize our recursive solution with the addition of a few simple steps. This greatly improves the solution since it reduces the time complexity down to polynomial from exponential.
Now let’s see how one would approach to write a tabulated solution.
c) Tabulation
The key concept of tabluation is to be able to build the store from bottom to top with the help of base conditions and the recursive logic.
From our discussions in this and this, we all know that we must keep following points in mind while writing a tabulated solution :
- The dimensions of store depends on the number of changing parameters in our recursive solution. Which in this case is 2 : target sum & N. Since target sum can take a total of S+1 and number of elements can take a total of N+1 possible values. Thus we have store[N+1][S+1].
- The easiest way to visualize store is to understand the fact that (in this case)in general store[n][s] holds the answer for the function call isSubsetSum(number_set, n, s).
- In order to get started, we must have something to build upon. Thus we need to initialize certain values of store. This is where the base conditions comes to the rescue. We initialize the store with the help of base conditions from the recursive solution.
- The filling up of store is done using the initialized values and the recursion logic. Thus finally obtaining the value of store[n][targetSum] which as we know, holds the answer for the original function call isSubsetSum(number_set, n, targetSum). Then we return the same.
With these points in mind, let’s see what a Tabulated solution (bottom-up approach) would look like.
That’s how the tabulated solution can be written by following the previously discussed steps and our knowledge from recursive solution.
With this we have come to an end of Subset Sum Problem. I hope the article was informative and helped you to properly understand the concept of DP and what should be the approach for writing a memoized and tabulated solution for the Subset Sum Problem.
