一、题目
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-’ before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-’ before 1 and concatenate them to build the expression “+2-1”.
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
二、题解
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum < target || ((target & 1) ^ (sum & 1)) == 1) return 0;
return f(nums,(target + sum) >> 1);
}
int f(vector<int>& nums,int t){
if(t < 0) return 0;
vector<int> dp(t+1,0);
dp[0] = 1;
for(auto num:nums){
for(int j = t;j >= num;j--){
dp[j] += dp[j-num];
}
}
return dp[t];
}
};
