• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

688

class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int num : nums) {
sum += num;
}

if(target < -sum || target > sum) return 0;

int[] dp = new int[2 * sum + 1];

dp[nums[0] + sum] = 1;
// [0,0,0,0,0,0,0,0,1]
dp[-nums[0] + sum] += 1;

for (int i = 1; i < nums.length; i++) {
int[] next = new int[2 * sum + 1];

for (int s = 0; s <= 2 * sum; s++) {
if (dp[s] > 0) {
next[s + nums[i]] += dp[s];
next[s - nums[i]] += dp[s];
}
}

dp = next;
}

return dp[target + sum];
}
}

class Solution {
int res = 0;

public int findTargetSumWays(int[] nums, int target) {
dfs(nums, 0, target, 0);
return res;
}

private void dfs(int[] nums, int start, int target, int curr){
if(start == nums.length){
if (target == curr) res++;
return;
}

dfs(nums, start + 1, target, curr + nums[start]);
dfs(nums, start + 1, target, curr - nums[start]);
}
}