Algorithm for Target Sum Problem using Dynamic Programming

In this article, we will cover a famous dynamic programming question, "Target Sum".
So Let's Start.

What is Target Sum Problem?

We are given some number say a,b,c,d.......n, also we are given a target that we need to make. This value i.e. target needs to be made using all the given numbers
This means we can either choose from a + or a - for every number so that we can make a total sum = Target!

Target Sum Problem example:

Example 1:
Input: [1,1,1,1,1] and target = 3
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Initial takes on the question:

• We need to reach the target using the given numbers
• We have to make a choice at every step we take, the choices are: Take the number as a positive or take it as a negative.
• We need to tell whether or not we can make the target value using these guys in the given array!
• Now the question looks like a pretty famous paradigm in Dynamic Programing called the 0/1 Knapsack problem.
• There is, however, a small yet important variation, our Knapsack capacity = Sum is obvious, but we need to take all the elements!
• So we don't have to see whether we choose an element or not, but choose whether to take it as a positive or take it as a negative!

Now that we have some idea of what the question is exactly about, let's try to analyze a bit more to gain a deeper insight of the code we are about to discuss.
So hold on for a moment and think, when have are you done with this question?
If you thought that when we have considered all the numbers and such a selection has been made that has made the total sum = target. Then we have won!
Well this is exactly what our terminating case/base case is!
Apart from these base cases, what is something that we repeatedly calculate? The sum!
Now note that we need both the negative possibilities as well as the positive possibilities!
This might sound tricky at this moment, but bear with me, an example walkthrough, and a diagram will clear it up for you!

For now just understand that we need to consider these two decisions:

• +ve cases sum : (arr, target, i-1, curr_sum + arr[i])
• -ve cases sum : (arr, target, i-1, curr_sum - arr[i])

For making it sink down inside your brain, I will go through one more example!
Say that we have the case [1,1,1] and the target we need to make = 2
Remember at each point we can either take the number as a positive or a negative, so lets try to understand it now! Let's look at the possiblities:

• At each point i.e. for each number I have to keep into account both cases: So we can take (+1)[1,1] and (-1)[1,1] as my first split.
• Now while doing such splits we need to keep track of the curr_sum at all times, for instance heree +1, -1 are the current sums for the two splits respectively
• For the first split, lets try and make one more split: (+1, +1)[1] and (+1, -1)[1] Making their respective current sum sas: 2, 0
• And this is exacly how our recursion will pan out, look at the diagram below.

Now a very important thing to note from the diagram, the yellow pairs I have drawn, for level i = 1, i = 2. Well that is actually repeated computation for a case that we have already seen, by case here I mean, a situation where my current_sum and the index I am dealing with both are same.
Now if in some way I could save these results for future computations, I can use them again and save some computations. That's memorization, Dynamic Programming! Boom! So we can safely begin to compute using pre computed results!

Implementation in Python: