494 - Target Sum

2020/04/04

leetcode

Problem

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.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Solution

DP problem. The hardest part of this problem is to find the states.

What states do we have to calculate the current result, which is the number of ways of reaching the target.

We need all the sum values of the previous number to calculate the current one.

for j in range(2sum+1):
    if dp[i-1][j] > 0: # only check the ones, which have been reached
      if j+nums[i] < 2sum + 1: # sign + to the current number, we transit from j to j+nums[i]
        dp[i][j+nums[i]] += dp[i-1][j]
      if j-nums[i] >= 0: # sign + to the current number, we transit from j to j-nums[i]
        dp[i][j-nums[i]] += dp[i-1][j]

We start from the offset.

# the first number with symbols
dp[0][offset+nums[0]] +=1
dp[0][offset-nums[0]] +=1

Important: You have to use += 1, not only = 1, because the number can be 0.

For exmaple: we take sum = 5 When the first number is 1 (not 0):

d[0][0+sum + 1] += 1 -> dp[0][6] = 1
d[0][0+sum - 1] += 1 -> dp[0][4] = 1

It means:

there is one ways to reach 1 (6 - offset)

there is one ways to reach -1 (4 - offset)

When the first number is 0:

d[0][0+sum + 1] += 1 -> dp[0][5] = 1
d[0][0+sum - 1] += 1 -> dp[0][5] = 2

It means there are 2 ways to reach 0 (5 - offset)

Solution 1: 2D - DP

class Solution():
    def findTargetSumWays(self, nums, S):
        l = len(nums)
        n = 2 * sum(nums) + 1
        offset = sum(nums)

        dp = [[0] * n for i in nums]

        if not nums:
            return 0

        # base case
        dp[0][offset - nums[0]] += 1
        dp[0][offset + nums[0]] += 1

        for i in range(1, len(nums)):
            for j in range(n):
                if dp[i-1][j] > 0:
                    if j + nums[i] < n:
                        dp[i][j + nums[i]] += dp[i-1][j]
                    if j - nums[i] >= 0:
                        dp[i][j - nums[i]] += dp[i-1][j]

        return dp[-1][offset + S]


print(Solution().findTargetSumWays([1, 1, 1, 1, 1], 3))

Time: O(l*n) Space: O(l*n)

Solution 2: 1D - DP

We notice that, to calculate the dp array at the current index, we only have to know one previous row.

So we only have to maintain two dp arrays to record previous values and current values respectly.

class Solution:
    def findTargetSumWays(self, nums, S):
        if not nums:
            return 0
        l = len(nums)
        n = 2 * sum(nums) + 1
        offset = sum(nums)
        dp = [[0] * n for i in nums]

        dp[0][offset + nums[0]] += 1
        dp[0][offset - nums[0]] += 1

        for i in range(1, l):
            for j in range(n):
                if dp[i - 1][j] > 0:
                    if dp[i - 1][j] < n:
                        dp[i][j + nums[i]] += dp[i - 1][j]
                    if dp[i - 1][j] >= 0:
                        dp[i][j - nums[i]] += dp[i - 1][j]

        return dp[-1][offset + S]

print(Solution().findTargetSumWays([1, 1, 1, 1, 1], 3))