LeetCode：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

思路

方法一：使用递归
方法二：使用动态规划，记数组的元素和为 sum，添加 - 号的元素之和为 a，则其余添加 + 的元素之和为 sum−a，得到的表达式的结果为(sum-a)-a = sum - 2a = target , res != -1检查memo数组是否已缓存了该子问题的解。如果有直接返回，c < nums[i]表示当前元素值大于负载值,无法选择当前元素。直接递归处理下一元素，如果negatives无法选择当前元素,考虑两种选择: 1，不选择当前元素,递归处理下一元素dfs(dfs, i-1, c) 。 2，选择当前元素,负载减去该元素值,递归dfs(dfs, i-1, c-nums[i])，则两种选择的方案数相加就是包含和不包含当前元素的总方案数。

代码

方法一

class Solution {
public:int count = 0;int findTargetSumWays(vector<int>& nums, int target) {backtrack(nums, target, 0, 0);return count;}void backtrack(vector<int>& nums, int target, int index, int sum) {if (index == nums.size()) {if (sum == target) {count++;}} else {backtrack(nums, target, index + 1, sum + nums[index]);backtrack(nums, target, index + 1, sum - nums[index]);}}
};

方法二

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int s = reduce(nums.begin(), nums.end(), 0) - abs(target);if (s < 0 || s % 2)return 0;int m = s / 2;int n = nums.size();vector<vector<int>> memo(n, vector<int>(m + 1, -1));auto dfs = [&](auto&& dfs, int i, int c) -> int {if (i < 0)return c == 0;int& res = memo[i][c];if (res != -1)return res;if (c < nums[i]) {return res = dfs(dfs, i - 1, c);}return res = dfs(dfs, i - 1, c) + dfs(dfs, i - 1, c - nums[i]);};return dfs(dfs, n - 1, m);}
};

总结

• 使用回溯可以遍历不同的方案，
• 问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 ’ - ’ 次数，计算选取元素的方案数，就可以使用动态规划了