Description

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:

  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.

Solutions

1. Brute Force - DFS

# Time: O(2^n)
# Space: O(n)
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        res = [0]
        self.dfs(nums, 0, S, res)
        return res[0]
    
    def dfs(self, nums, i, S, res):
        if i == len(nums):
            if S == 0:
                res[0] += 1
            return
        self.dfs(nums, i + 1, S + nums[i], res)
        self.dfs(nums, i + 1, S - nums[i], res)

# Time Limit Exceeded
# 51/139 cases passed (N/A)

2. DP

# Time: O(n^2)
# Space: O(n^2)
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if not nums:
            return 0
        all_sum = sum(nums)

        if all_sum < S or S < -all_sum:
            return 0
        n = len(nums)
        dp = [[0 for _ in range(2 * all_sum + 1)] for _ in range(n + 1)]
        dp[0][all_sum] = 1
        left, right = 0, 2 * all_sum + 1
        for i in range(1, n+1):
            for j in range(left, right):
                if j + nums[i - 1] < right:
                    dp[i][j] += dp[i - 1][j + nums[i - 1]]
                if j - nums[i - 1] >= left:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]
        return dp[n][all_sum + S]

# 139/139 cases passed (1320 ms)
# Your runtime beats 5.01 % of python3 submissions
# Your memory usage beats 91.67 % of python3 submissions (13.1 MB)

  优化一下遍历范围:

# Time: O(n^2)
# Space: O(n^2)
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if not nums:
            return 0
        all_sum = sum(nums)

        if all_sum < S or S < -all_sum:
            return 0
        n = len(nums)
        dp = [[0 for _ in range(2 * all_sum + 1)] for _ in range(n + 1)]
        dp[0][all_sum] = 1
        right = 2 * all_sum + 1
        for i in range(n):
            for j in range(nums[i], right - nums[i]):
                if dp[i][j]:
                    dp[i + 1][j + nums[i]] += dp[i][j]
                    dp[i + 1][j - nums[i]] += dp[i][j]
        return dp[n][all_sum + S]

# 139/139 cases passed (364 ms)
# Your runtime beats 47.05 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13 MB)
# Time: O(n^2)
# Space: O(n)
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if not nums:
            return 0
        all_sum = sum(nums)

        if all_sum < S or S < -all_sum:
            return 0
        n = len(nums)
        # dp[i] represents number of possible ways to reach target i
        dp = [0 for _ in range(2 * all_sum + 1)]
        dp[all_sum] = 1
        right = 2 * all_sum + 1
        for i in range(n):
            tmp_dp = [0 for _ in range(2 * all_sum + 1)]
            for j in range(nums[i], right - nums[i]):
                if dp[j] != 0:
                    tmp_dp[j + nums[i]] += dp[j]
                    tmp_dp[j - nums[i]] += dp[j]
            dp = tmp_dp
        return dp[all_sum + S]

# 139/139 cases passed (308 ms)
# Your runtime beats 57.03 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

3. Subset

# Time: O(n^2)
# Space: O(n)
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if not nums:
            return 0
        count = collections.Counter({0:1})
        for num in nums:
            step = collections.Counter()
            for cnt in count:
                step[cnt + num] += count[cnt] 
                step[cnt - num] += count[cnt]
            count = step
        return count[S]
# 139/139 cases passed (320 ms)
# Your runtime beats 55.02 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)

4. 其他解法

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        # the same as P416, just consider target as (S + sum(nums))//2
        # the problem becomes find the + numbers s.t the sum is target
        # the rest are assigned with - 
        if (S + sum(nums)) % 2 == 1 or S > sum(nums):
            return 0
        else:
            target = (S + sum(nums))//2
        dp = [0]*(target+1)      
        dp[0] = 1
        for num in nums:
            for j in range(target,num-1,-1):
                dp[j] += dp[j-num]
                
        return dp[target]

References

  1. 494. Target Sum
  2. DP
  3. huahua
  4. Subset