494. Target Sum
难度: 中等
刷题内容
原题连接
- https://leetcode.com/problems/target-sum
内容描述
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.
解题方案
思路 1
递归，findSum(s, start_idx) 函数的意思是从start_index开始向后的子集合能有几种得到s的方法
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
def findSum(s, start_idx):
if start_idx == len(nums):
return 1 if s == 0 else 0
return findSum(s+nums[start_idx], start_idx+1) + findSum(s-nums[start_idx], start_idx+1)
return findSum(S, 0)
但是这样会超时，所以用cache 记一下
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
def findSum(s, start_idx):
if start_idx == len(nums):
return 1 if s == 0 else 0
if (s, start_idx) not in cache:
cache[(s, start_idx)] = findSum(s+nums[start_idx], start_idx+1) + findSum(s-nums[start_idx], start_idx+1)
return cache[(s, start_idx)]
cache = {}
return findSum(S, 0)
思路 2
首先我们要找到一个集合 X 的正sum和其补集 Y 的负sum之和为target. - 则有 sum(X) - sum(Y) = target - 又有 sum(X) + sum(Y) = sum(nums) - ---> 因此由 1 式和 2 式证得：sum(X) = (sum(nums) + target) / 2
因此题目就变成了找到了一个subset的正sum为(sum(nums) + target) / 2
于是动态规划，利用leetcode416题的思想
但是这次dp[i]代表的是能够找出几个subset的sum等于i, 例如dp[0] = 1是必然的，因为我们只能取空子集，才能得到sum为0
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
def subsetSum(s):
dp = [0] * (s+1)
dp[0] = 1
for i in range(len(nums)):
for j in range(s, nums[i]-1, -1):
dp[j] += dp[j-nums[i]]
return dp[-1]
if sum(nums) < S or (S+sum(nums)) % 2 > 0:
return 0
return subsetSum((S+sum(nums))/2)
