494.目标和

https://leetcode-cn.com/problems/target-sum/

一：暴力遍历（回溯）

py超时，但java没有

从0开始递归数组，直到n位置终止，每次分别回溯尝试+和-

class Solution:
    def findTargetSumWays(self, nums, target: int) -> int:
        self.res = 0	#全局计数
        def bt(start, sum):
            if start  == len(nums):	#递归出口
                if sum == target:
                    self.res += 1	#满足条件，结果加一
                return
            #注意不要直接修改sum，即“保存现场”
            bt(start+1, sum+nums[start])	#加号
            bt(start+1, sum-nums[start])	#减号
        #开始
        bt(0, 0)
        return self.res

二：dp

记数组的元素和为sum，添加-号的元素之和为neg，则其余添加 + 的元素之和为sum-neg。由题意，有：

(sum−neg)−neg = sum−2*neg = target

即

neg = (sum−target)/2

题目中nums元素非负，因此neg也非负，当sum−target为负直接返回0

问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数。是一个01背包问题，可以用dp

与416. 分割等和子集类似，设dp[i][j] 表示在数组nums 的前 i个数中选取元素，使得这些元素之和等于 j 的方案数，i=0表示不取，因此i=1表示数组0号元素，即dp[i][j]表示能否用数组[0...i-1]凑出，dp方程为

dp[i][j] =  dp[i-1][j]    +    dp[i-1][j-nums[i-1]]
              不用i-1                   用i-1

base case：

dp[0][j] = 0	#0个数什么也凑不出
dp[i][0] = 1	#凑出0有一种方案

最终所求为dp[n][neg]（n为nums长度）

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        diff = s - target
        if diff < 0 or diff % 2 != 0:   #无法构造
            return 0
        neg = diff // 2
        n = len(nums)
        dp = [[0] * (neg+1) for i in range(n+1)]
        for i in range(n+1):	#关键，base case
            dp[i][0] = 1
        for i in range(1, n+1):
            for j in range(neg+1):
                if j-nums[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][neg]