头脑风暴：目标和

题目

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3输出：5

解释：

-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

一共有 5 种方法让最终目标和为 3。

提示：

• 数组非空，且长度不会超过 20 。

• 初始的数组的和不会超过 1000 。

• 保证返回的最终结果能被 32 位整数存下。

解题思路

假设加法的总和为 x，那么减法对应的总和就是 sum - x。所以我们要求的是 x - (sum - x) = S，可以推导出：x = (S + sum) / 2。

因此，本问题就可以转化为，装满容量为 x 背包，有几种方法。

如果 (S + sum) / 2 不为整数，此时是没有解决方案的；并且如果目标数 S 大于 sum ,此时也是无解的。

本题需要求解的是装满背包，总共有几种方法，这就是一种组合问题了。

第一步，确定 dp 数组以及下标的含义：p[j] 表示：填满 j 这么大容积的包，有 dp[j]种方法。

第二步，确定递推公式：求组合类问题的公式一般为 dp[j] += dp[j - nums[i]]。

第三步，dp 数组初始化：在初始化的时候 dp[0] 一定要初始化为 1，因为 dp[0]是在公式中一切递推结果的起源，dp[0] = 1，理论上也很好解释，装满容量为 0 的背包，有 1 种方法，就是装 0 件物品。

第四步，确定遍历顺序：对于 01 背包问题一维 dp 的遍历，nums 放在外循环，target 在内循环，且内循环倒序。

代码实现

class Solution {    public int findTargetSumWays(int[] nums, int target) {        int sum = 0;        for (int i = 0; i < nums.length; i++) sum += nums[i];        if ((target + sum) % 2 != 0) return 0;        int size = (target + sum) / 2;        if(size < 0) size = -size;        int[] dp = new int[size + 1];        dp[0] = 1;        for (int i = 0; i < nums.length; i++) {            for (int j = size; j >= nums[i]; j--) {                dp[j] += dp[j - nums[i]];            }        }        return dp[size];    }}

最后

• 时间复杂度：O(n × m)，n 为正数个数，m 为背包容量

• 空间复杂度：O(m)，m 为背包容量