Hard to understand the dynamic programming part of Leetcode question 494, Target Sum

Question

I found this solution which is extremely fast(beats 99.5%) and space-saving(beats 95%) at the same time. I understand most part, except the line: dp[j]=dp[j]+dp[j-num]

I understand the w is calculating the sum of all numbers with '+' sign.

Can anyone explain what this part means? dp[j]=dp[j]+dp[j-num]

Here is the code:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        w=(S+sum(nums))//2
        if (S+sum(nums))%2==1: return 0
        if sum(nums)<S: return 0
        dp=[0]*(w+1)
        dp[0]=1
        for num in nums:
            for j in range(w,num-1,-1):
                dp[j]=dp[j]+dp[j-num]
        return dp[-1]

Here is the question:

 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. 
For each integer, you should choose one from + and - as its new symbol.
    
Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 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.

Answer 1

Rather than attempting to theorize about why this works, I'm just gonna walk through the logic and describe it. In your example, nums = [1, 1, 1, 1, 1]

w=(S+sum(nums))//2       # in your example this is 4
dp=[0]*(w+1)             # your array is 5 elements long, its max index is w 
dp[0]=1                  # initialize first index to 1, everything else is 0 
        
for num in nums:                   # num will be 1 for 5 iterations
    for j in range(w,num-1,-1):    # j starts at the end and iterates backward. 
                                   # here j goes from index 4 to 0 every time
        dp[j]=dp[j]+dp[j-num].     # remember dp = [1, 0, 0, 0, 0]. but after 
                                      # the first completion of the inner loop, dp 
                                      # will be [1, 2, 0, 0, 0]. remember you have 
                                      # negative indices in this language. 
return dp[-1]          # so after all iterations... dp is [1, 2, 3, 4, 5] 

you're just kind of pushing that initial 1 - i.e. dp = [1, 0, 0, 0, 0] - toward the end of the array. And this is happening in a way that is dependent on the size of num is, at each iteration.

---

Why does this work? Let's try a different example and see the contrast. Let's say nums = [7, 13] and S is 20. The answer should be 1, right? 7 + 13 = 20, that's all that is possible.

w=(S+sum(nums))//2       # now this is 20.
dp=[0]*(w+1)             # your array is 21 elements long, its max index is w 
dp[0]=1                  # initialize first index to 1, everything else is 0 
        
for num in nums:                   # so num will be 7, then 13, 2 iterations
    for j in range(w,num-1,-1):    # j starts at the end and iterates backward. 
                                   # on first iteration j goes from index 20 to 6
                                   # on 2nd iteration j goes from index 20 to 12 
        dp[j]=dp[j]+dp[j-num].     # so when num = 7, and you reach the 2nd last 
                                     # iteration of the inner loop... index 7 
                                     # you're gona set dp[7] to 1 via dp[7]+dp[0]
                                     # subsequently, when num = 13... when you're 
                                     # at dp[20] you'll do dp[20] = d[20]+d[7]. 
                                     # Thus now dp[20] = 1, which is the answer.
return dp[-1]

So the larger num is... the more you skip around, the less you move 1s up to the top. The larger num values disperse the possible combinations that can add up to a given S. And this algorithm accounts for that. But notice the manner in which the 1 at dp[0] was moved up to dp[20] in the final example. It was precisely because 7 + 13 = 20, the only combination. These iterations and summations account for all these possible combinations.

But how are potential sign flips accounted for in the algorithm? Well, let's say S was not 20 in the previous, but it was 6. i.e. 13 - 7 = 6, the only solution. Well... lets look at that example:

w=(S+sum(nums))//2       # now this is 13. (20+6)/2 = 13.
dp=[0]*(w+1)             # your array is 14 elements long 
dp[0]=1                  # initialize first index to 1 again

for num in nums:             # so num will be 7, then 13, 2 iterations
    for j in range(w,num-1,-1):    
                           # j starts at the end and iterates backward. 
                           # on first iteration j goes from index 13 to 6
                           # on 2nd iteration j goes from index 13 to 12 
        dp[j]=dp[j]+dp[j-num]. 
                           # so this time, on the 2nd iteration, when 
                           # num = 13... you're at dp[13] 
                           # you'll do dp[13] = d[13]+d[0]. 
                           # Thus now dp[13] = 1, which is the answer.
                 # This time the 1 was moved directly from d0 to the end

return dp[-1]

So this time, when the combination included a negative number, it was the size of w being 13 that led to the solution: the index d[13] + d[0] = 1. The array size was smaller such that the larger number added with 1 directly.

It's quite odd, I will admit, you have 2 different mechanisms working depending on how what the signs are, potentially. In the case of a positive and negative number summing to S, it was the smaller overall array length that led to the 1 moving to the final slot. For 2 positive numbers... there was this intermediary moving the 1 up that happened. But at least you can see the difference...

Answer 2

Sahadat's answer is correct but may not be comprehensive enough for OP. Let me add more details. The mathematical equivalent question is how to choose certain elements from the list to sum to w (no changing signs). This question is however easier to deal with in DP. IN particular, d[0]=1 since we have unique way to reach 0 (by choosing no element). After that, inductively, for each num we process, we know the number of solutions to reach j is either d[j] (meaning we DO NOT choose num) or d[j-num] (meaning we do choose num). Once we go over all nums in the list, d[w] will contain the number of solutions to reach w. This is also the solution to the original question.