Title:

Give you an integer array nums and an integer target.

Add '+' or '-' before each integer in the array, and then concatenate all integers to construct an expression:

For example, nums = [2, 1], you can add '+' before 2 and '-' before 1, and then concatenate them to get the expression "+ 2-1".
Returns the number of different expressions that can be constructed by the above method and whose operation result is equal to target.

 

Example 1:

Input: num = [1,1,1,1,1], target = 3
Output: 5
Explanation: there are five ways to make the final goal sum to 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: num = [1], target = 1
Output: 1

Solution:

Method 1:

enumeration

import java.util.*;
class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        calculate(nums, 0, 0, target);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int target) {
        if (i == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], target);
            calculate(nums, i + 1, sum - nums[i], target);
        }
    }
}
/**
 * @author wyl
 */
public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,1,1,1,1};
        int target = 3;
        int res = s.findTargetSumWays(nums, target);
        System.out.println(res);
    }
}

Method 2:

Dynamic programming -- 01 knapsack problem

For the template of knapsack problem, please refer to this link: https://leetcode-cn.com/problems/target-sum/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-wa5r/

Template for backpack classification:

1. 0 / 1 knapsack: outer loop num, inner loop target,target in reverse order, and target > = num [i];
2. Complete knapsack: outer loop num, inner loop target,target in positive order and target > = num [i];

Template for problem classification:

1. Maximum value problem: DP [i] = max / min (DP [i], DP [i-num] + 1) or DP [i] = max / min (DP [i], DP [i-num] + Num);
2. Bool: DP [i] = DP [i] | DP [i-num];
3. Combinatorial problem: dp[i]=dp[i]+dp[i-num];

We want S = positive and - negative and = x - y
It is known that the sum of X and Y is the sum of arrays: x + y = sum, and y = sum - x is obtained

The following equations are solved:
You can find x = (S + sum) / 2 = target
That is, we need to select several numbers from the num array and make the sum of them target (given indirectly by target).
So it is transformed into whether the numbers in num can be combined into target, 01 knapsack problem. The outer loop is the selection pool num and the inner loop is the target.
dp[i] indicates that there are dp[i] kinds of num combinations with sum as I.

The outer layer traverses each num;
The inner layer traverses the target (from large to small).
For each arrangement where the sum of elements is equal to i - num, an arrangement where the sum of elements is equal to I can be obtained after adding num finally. Therefore, when calculating dp[i], the sum of all dp[i − num] should be calculated.
dp[i] = dp[i] + dp[i - num]
For boundary conditions, we define dp[0] = 1, which means that the sum of elements is 0 only when no element is selected, so there is only one scheme.
Finally, dp[target] is returned

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (S > sum || (S + sum) % 2 == 1) {
            return 0;
        }
        int target = (S + sum) / 2;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

/**
 * @author wyl
 */
public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        int res = s.findTargetSumWays(nums, target);
        System.out.println(res);
    }
}