10-9 LeetCode 494. Target Sum
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.
給你一個列表和一個目標整數(shù) S，列表元素都是非負整數(shù)台夺，你有+和-兩個符號，對列表里的每一個整數(shù)，你需要選擇其中一個符號作為他的符號。
找出一共有多少種方法來分配符號是列表元素的和等于目標整數(shù)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 lengThe 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 1():
幾乎所有題目都可以使用蠻力法窘奏，我用遞歸和循環(huán)兩種方式去使用蠻力法，結(jié)果都沒有解決葫录，都超時了着裹。。米同。骇扇。。
超時代碼如下：
`class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if not nums:
return 0
front = [nums[0], -nums[0]]
for i in range(len(nums))[1:]:
length = len(front)
for j in range(length):
front.append(front[j]-nums[i])
front[j] = front[j] + nums[i]
count = 0
for num in front:
if num == S:
count += 1
return count`
然后就想著如何優(yōu)化這種方法窍霞，于是用字典這種數(shù)據(jù)結(jié)構(gòu)代替列表匠题，這樣就可以在循環(huán)的過程中直接求出方法數(shù)，省去最后一個for sum in front循環(huán)但金，畢竟這個數(shù)據(jù)非常大韭山。
改進代碼如下：
`class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if not nums:
return 0
dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0 : 2}
for i in range(1, len(nums)):
temp_dic = {}
for d in dic:
temp_dic[d + nums[i]] = temp_dic.get(d + nums[i], 0) + dic.get(d, 0)
temp_dic[d - nums[i]] = temp_dic.get(d - nums[i], 0) + dic.get(d, 0)
dic = temp_dic
return dic.get(S, 0)`
Solution 2
這是參考了大神的做法。
Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation
先根據(jù)數(shù)學的關(guān)系冷溃，將問題優(yōu)化钱磅。
集合P包括所有符號為正的整數(shù)，集合N包括所有符號為負的整數(shù)似枕「堑可以得出如下關(guān)系：
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2*sum(P) = target + sum(nums)
于是這題目就變成求有多少中子集合的和為 (target + sum(nums))/2。 具體過程參考鏈接凿歼。
感想
這是第一次寫褪迟，寫的不是很好。主要是時間緊答憔，對問題沒有那么多時間分析味赃，也是一個摸索的階段，在摸索如何寫的精簡和易懂虐拓，畢竟大家都很忙心俗。謝謝閱讀！
