494. Target Sum

You are given a list of non-negative integers, $a_1, a_2, \cdots, a_n$, 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:

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:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

Solution: DP

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return 0

        total = sum(nums)
        target = abs(target)
        if total < target or (total + target) & 1:
            return 0

        rows = len(nums) + 1
        cols = total + 1

        # dp[i][j] is ways of nums[:i] to form j
        dp = [[0] * cols for _ in xrange(2)]
        dp[1][nums[0]] = 2 if nums[0] == 0 else 1

        for k in xrange(2, rows):
            num = nums[k - 1]
            k %= 2
            for tar in xrange(cols):
                if tar > num:
                    dp[k][tar] = dp[k - 1][tar - num]
                else:
                    dp[k][tar] = dp[k - 1][num - tar]
                if tar + num < cols:
                    dp[k][tar] += dp[k - 1][tar + num]

        return dp[(rows - 1) % 2][target]

Lessons:

• If target is negative, it has a same answer as abs(target). Simply reverse all operators.
• If total is odd and target is even, or vice versa, there is no way to get target.
• There are two ways to form 0 from 0, +0 or -0.
• Use rotated index to shrink dp size to O(n), and don't forget the return value might not in the last row.
• During DP, k - 1 numbers can form either target + num or target - num.