当前位置：网站首页>头脑风暴：目标和

头脑风暴：目标和

2022-08-10 14:51:00 【InfoQ】

题目

给定一个非负整数数组，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];
 }
}