494. 目标和

目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

解题思路：

解法一：回溯算法
直接暴力递归搜索

class Solution {
    int result = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return result;
    }
    public void dfs(int[] nums, int target, int start, int sum) {
        if (start == nums.length) {
            //遍历完毕，如果sum等于target，结果加一
            if (sum == target) {
                result++;
            }
            return;
        }
        dfs(nums, target, start + 1, sum + nums[start]); //加上当前数
        dfs(nums, target, start + 1, sum - nums[start]); //减去当前数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二：转化为背包问题，使用动态规划
记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为 sum−neg，得到的表达式的结果为
(sum−neg)−neg=sum−2*neg=target
即neg= (sum−target)/2
由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数，所以上式成立的前提是 sum−target 是非负偶数。若不符合该条件可直接返回 0。
若上式成立，问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于neg，计算选取元素的方案数。我们可以使用动态规划的方法求解。
此时问题就转化为，装满容量为neg背包，有几种方法。
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法。
确定递推公式：
不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。
那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。
那么凑整dp[j]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
即dp[j] += dp[j - nums[i]]。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {return 0;}
        int neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = neg; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[neg];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19