Find Number of Sub-Sets That Add Up To A Target Sum - Dynamic Programming

Problem Definition

Given an array of positive integers greater than 0, find the number of subsets whose sum is equal to a given target sum.

input[] = {2, 7, 9, 12, 14, 7}
target sum = 14

output: 3
Explanation: There are 3 subsets that sum to 14. These are {2, 12}, {14}, {7, 7}

This can be solved using Recursion and Dynamic Programming. First recursion will be applied, then to minimize the complexity, DP is used to store and retrieve the already computed values.

Recursion

To compute subset, during the iteration of given array, at each item we have a choice whether the item will be in the subset or not.
If we decide to include the item in subset, then new target sum will be targetSum - item.
If we decide not to include the item, then the we need to keep on looking for the same target sum.

In other word, for an index i,

total subsets = total subsets that includes input[i] + total subsets that excludes input[i]

This is relation we will use for the recursion.

Recursive Solution

Time Complexity

Time complexity is determined by the number of times the recursive method compute() is called. Problem here is the method compute() is called over and over again for the same arguments. The Time Complexity for this recursive method will be ${\cal O}(2^n)$ which is exponential.

Obviously this is not an efficient solution. Since we calling the method compute() over and over again for the same arguments, we can optimize our solution using Dynamic Programming,Memoization in this case by memorizing the intermediate results.

Recursive Solution with Dynamic Programming

Time Complexity

Again, time complexity is determined by the number of times the recursive method computeDP() is called. Unlike previous method, now at most this method will be called $n \times targetSum * 2$ where $n$ is number of elements in the input array.

So the Time Complexity is ${\cal O}(n * targetSum)$ time.

---

---

---