Leetcode 494. Objectives and

494. Objectives and

Give you an array of integers nums And an integer target .

Add... Before each integer in the array ‘+’ or ‘-’ , And then concatenate all the integers , You can construct a expression ：

for example ,nums = [2, 1] , Can be in 2 Before adding ‘+’ , stay 1 Before adding ‘-’ , And then concatenate them to get the expression “+2-1” .
Returns the 、 The result is equal to target Different expression Number of .

Example 1：

Input ：nums = [1,1,1,1,1], target = 3
Output ：5
explain ： Altogether 5 Ways to make the ultimate goal and 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

Ideas

This problem feels like dividing the elements in the array into two parts , Then take their difference , Find the difference equal to target The combination number of .
That is, find the number of methods to fill the backpack , It's usually dp[j] += dp[j - nums[i]];
First analyze the special situation , If sum Less than target The absolute value of ,namo You can't make it up , Go straight back to 0 that will do
We divided the set into two parts , Add subtract , Let the sum on the left be equal to L that The sum on the right is equal to R ,L + R = sum
L - (sum - L) = target namely L = (sum + target) / 2;
sum and target It's all known , So we can find out L This is the capacity of the backpack

Again because L It must be an integer , therefore (sum + target) It must be an even number , If it's odd , direct return 0 that will do
dp[i] meaning ： manage to put together i Altogether dp[i] Methods
The recursive formula ：dp[j] += dp[j - nums[i]];
initialization ： dp[0] = 1, Make up 0 There is only one way

Code

class Solution {
    
public:
    //  There are several ways to fill a backpack  dp[j] += dp[j - nums[i]];
    //  Join in  L Is the sum of positive numbers   Then there is  R Is the sum of negative numbers , Not looking at the symbols adds up to sum
    //  therefore  L - (sum - L) = target,sum and target Is constant , therefore 
    // L = (target + sum) / 2;
    // L Is the maximum capacity of the backpack 
    int findTargetSumWays(vector<int>& nums, int target) {
    
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        //  If target Greater than sum There is no plan 
        if (abs(target) > sum) return 0;

        int L = (sum + target) / 2;
        //  because  L  It must be an integer , therefore (sum + target)  It must be an even number 
        if ((sum + target) & 1) return 0;

        int dp[L + 1]; // dp[i]  Make a sum  i  common  dp[i]  Methods 
        for (int i = 0; i <= L; i++) dp[i] = 0;
        dp[0] = 1; //  Array initialization , And for  0  share  1  Methods 

        for (int i = 0; i < nums.size(); i++) {
    
            for (int j = L; j >= nums[i]; j--) {
    
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[L];
    }
};