原文链接: https://leetcode-cn.com/problems/YaVDxD

中文题目

给定一个正整数数组 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

 

注意：本题与主站 494 题相同： https://leetcode-cn.com/problems/target-sum/

通过代码

高赞题解

我总结了剑指Offer专项训练的所有题目类型，并给出了刷题建议和所有题解。

在github上开源了，不来看看吗？顺道一提：还有C++、数据结构与算法、计算机网络、操作系统、数据库的秋招知识总结，求求star了，这对我真的很重要？

$\Rightarrow$通关剑2

解题思路

背包问题串讲
这道题的关键是看出来可以用背包来做，否则搜索就只有回家凉快去了。
假设加上’+’的数字之和是pos，前面加’-‘数字之和neg， 所有数字之和为sum
符合条件的情况有：
pos - neg = target
等价：
pos - (sum - pos) = tar
2pos - sum = tar
pos = (target + sum) / 2

需要注意的是这里都是整数运算，不能舍，因此如果target + sum是奇数，则一定不可能，直接返回0

因此我们的物品还是nums数组，但是背包容量变成了pos，这就是我们要凑成的情况，并且这道题是组合，先遍历物品（见上面超链接里解析）

代码

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((target + sum) & 1) return 0;
        int cap = (sum + target >> 1);
        vector<int> dp(cap + 1);
        dp[0] = 1;
        for (const int& num : nums)
            for (int i = cap; i >= num; --i) {
                dp[i] += dp[i - num];
            }
        return dp[cap];       
    }
};

统计信息

通过次数	提交次数	AC比率
2438	4105	59.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言