给你一个非负整数数组 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
DP:
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int total = 0;for(int n : nums){total += n;}if((total + target) % 2 != 0 || total < abs(target)){return 0;}int sub = (total + target) / 2;vector<int> dp(sub + 1, 0);dp[0] = 1;for(int n : nums){for(int j = sub; j >= n; j--){dp[j] += dp[j - n];}}return dp[sub];}};
(total + target) % 2 != 0
:
如果 total + target
是奇数,那么无法将它分割成两部分,返回 0
。
将 nums
划分为两个子集:一个子集 P
代表带正号的部分。另一个子集 N
代表带负号的部分。
根据题目要求,这两个子集满足:
- P − N=target
- P + N = sum(nums)
通过这两个方程,我们可以推导出 P
的值:
P
=(sum(nums) + target) / 2
为了确保 P
是一个整数,(sum(nums) + target)
必须是偶数。如果 (sum(nums) + target)
是奇数,那么 P
就会是一个小数,在这种情况下,问题无解,直接返回 0
。
total < abs(target)
:
如果 total
小于 target
的绝对值,则无法通过 +
和 -
来组合出 target
,所以直接返回 0
。
这就变成了一个子集和问题:计算所有可以构成和为 sub
的子集数目。
定义dp[i]
表示可以组成和为 i
的子集数目。
初始时,dp[0] = 1
,表示可以通过一个空集来组成和为 0
的子集。所有其他 dp[i]
(对于 i > 0)都为 0
,因为还没有计算任何子集。
为什么从 sub
开始倒序遍历?
- 为了避免当前的元素
n
被重复使用。假设我们正在处理元素n
并且当前正在更新dp[j]
,如果我们从dp[sub]
开始遍历并往下计算,就可以确保每次计算时,dp[j - n]
只会使用上一轮的值。 - 如果我们从小到大遍历,可能会在同一轮循环中多次使用同一个元素
n
,这会导致错误的计算。
dp[j] += dp[j - n]
的含义:
dp[j - n]
代表当前元素n
加入之前,可以组成和为j - n
的子集数量。- 加上
n
后,和变为j
,因此可以通过将dp[j - n]
加到dp[j]
上,来表示有多少个子集和为j
。 - 换句话说,
dp[j]
就是之前可以组成和为j - n
的子集数目与当前元素n
组合后组成和为j
的子集数目的和。
举个例子:
nums = [1, 2, 3]
, sub = 4
,那么 dp
数组初始化为:
dp = [1, 0, 0, 0, 0]
第一次循环,n = 1:
dp[4] += dp[4 - 1] = dp[3]
→ dp[4] = 0
dp[3] += dp[3 - 1] = dp[2]
→ dp[3] = 0
dp[2] += dp[2 - 1] = dp[1]
→ dp[2] = 0
dp[1] += dp[1 - 1] = dp[0]
→ dp[1] = 1
第二次循环,n = 2:
dp[4] += dp[4 - 2] = dp[2]
→ dp[4] = 0
dp[3] += dp[3 - 2] = dp[1]
→ dp[3] = 1
dp[2] += dp[2 - 2] = dp[0]
→ dp[2] = 1
第三次循环,n = 3:
dp[4] += dp[4 - 3] = dp[1]
→ dp[4] = 1
dp[3] += dp[3 - 3] = dp[0]
→ dp[3] = 2
最后:
dp = [1, 1, 1, 2, 1] , dp[sub] = dp[4] = 1
DFS:
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {return dfs(nums, target, 0, 0);}int dfs(vector<int>& nums, int target, int i, int sum){if(i == nums.size()){return sum == target ? 1 : 0;}int a = dfs(nums, target, i + 1, sum + nums[i]);int b = dfs(nums, target, i + 1, sum - nums[i]);return a + b;}
};