题目地址：

https://www.lintcode.com/problem/target-sum/description

给定一个非负整数的数组$A$，再给定一个目标值$t$，允许在$A$的数字间加正负号（第$0$个数字前也可以加正负号），问多少种符号的加法可以使得表达式的值恰好为$t$。

法1：DFS + 剪枝。直接枚举每个数字前是正号还是负号即可，一旦得到了$t$就计数加$1$。剪枝的方法是，如果对于$A[0:i]$已经得到了一个和$s$，那么显然有$s-{\sum }_{j=i+1}^{l_A}A[j]\le t\le s+{\sum }_{j=i+1}^{l_A}A[j]$，也就是说$|t-s|\le {\sum }_{j=i+1}^{l_A}A[j]$。为了剪枝，只需要预处理一下后缀和即可。代码如下：

public class Solution { private int res; /** * @param nums: the given array * @param s: the given target * @return: the number of ways to assign symbols to make sum of integers equal to target S */ public int findTargetSumWays(int[] nums, int s) { // Write your code here // 预处理后缀和 int[] suffSum = new int[nums.length]; for (int i = nums.length - 1; i >= 0; i--) { suffSum[i] = nums[i]; if (i + 1 < nums.length) { suffSum[i] += suffSum[i + 1]; } } dfs(0, 0, nums, s, suffSum); return res; } private void dfs(int pos, int curSum, int[] nums, int s, int[] suffSum) { // 枚举到最后一个数了，如果和恰好是s，则计数加一；然后return if (pos == nums.length) { if (curSum == s) { res++; } return; } // 满足剪枝条件则剪枝，否则继续DFS if (Math.abs(s - curSum) <= suffSum[pos]) { dfs(pos + 1, curSum + nums[pos], nums, s, suffSum); dfs(pos + 1, curSum - nums[pos], nums, s, suffSum); } } }

时间复杂度$O(2^n)$，空间$O(n)$。

法2：动态规划。这个问题可以视作是背包问题，但由于计算若干步的时候可能会得到负数，所以我们可以先算出$A$的数字和（假设和是$s$），然后将$A$中前$i$个数得到的结果加上$s$，显然前$i$个数得到的结果加上$s$一定是非负数了。设$f[i][j]$是$A$的前$i$个数运算（$i$从$1$开始计数），得到结果为$j-s$的方案数，那么$f[0][s]=1$，并且：$$f[i][j]=f[i-1][j-A[i-1]]+f[i-1][j+A[i-1]]$$代码如下：

public class Solution { /** * @param nums: the given array * @param s: the given target * @return: the number of ways to assign symbols to make sum of integers equal to target S */ public int findTargetSumWays(int[] nums, int s) { // Write your code here int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } if (sum < Math.abs(s)) { return 0; } int[][] dp = new int[nums.length + 1][(sum << 1) + 1]; dp[0][sum] = 1; for (int i = 0; i < nums.length; i++) { for (int j = 0; j <= sum << 1; j++) { if (j - nums[i] >= 0) { dp[i + 1][j] += dp[i][j - nums[i]]; } if (j + nums[i] <= sum << 1) { dp[i + 1][j] += dp[i][j + nums[i]]; } } } return dp[nums.length][sum + s]; } }

时空复杂度$O(ns)$，$n$为数组长度，$s$为数组的和。