494. Target sum · depth first search · knapsack problem

link ：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

Example

Ideas

Their thinking

1. Depth-first search

It is easy to think of when you see the topic dfs Violence enumerates every element , There are two situations for each element

• Is a positive number --> Add the previous enumeration
• It's a negative number --> Subtract the cases enumerated before

Finally, when enumerating to the last element, judge whether the condition is satisfied , Satisfy +1, dissatisfaction +0.

2. Dynamic programming , Convert to 0 1 knapsack problem

 

The topic needs to split the non empty array nums Is two arrays , This array partition makes the sum of the elements of the two subsets equal .
You can change the topic to , take nums After summing the array , Divide by half , Then in the array nums Whether it is possible to find the accumulation and equality of any element in , The only element that does not repeat the selection
In fact, after changing the topic and Change for The topic idea is almost . It's all about backpacking
It's equivalent to giving us a backpack with limited capacity and a pile of things , We need to put these things in our backpacks , Now we just need to judge whether it can be exactly filled , I don't care what's in it , How much is it loaded .
So we apply for two-dimensional dp[i][j] Array , Record what we can pack on this back , Is it full , There are two states when you meet something

1. Not loaded ：

• dp[i][j] = dp[i-1][j], I didn't install it. I inherited the last backpack state

2. installed :

• Just full dp[i][j] = true
• Yes, but not yet full ：dp[i][j] = dp[i-1][j-nums[i]], I packed it , Judge if there is anything else I can fill with this stuff

For example, the size of the backpack is 5, There's something 1,2,3,4( It has nothing to do with the subject ),dp[i][j] It means that the backpack is big j when , Chose something i, The current backpack is full (true), Still not full (false), therefore dp[1][2] by true, It means I chose something 2 And the size of the backpack is 2 when , My backpack is full , therefore dp[2][3]=true, that dp[2][5] = dp[2][3] + dp[1][2] = true, My backpack is 5, You can choose to pack things 3 And things 2, When the size of the backpack can't hold my things, inherit i-1 Backpack status , Because I can choose not to install the current thing , Then the backpack will not change , And so on , Finally back to dp[][max_j] Full or not
Space compression
You can see that from the top , We don't care what's in the backpack , Then is it unnecessary to apply for recording the size of the contents , Of course you can , We only care about whether the backpack can be filled , So we apply dp[n] Record the backpack size as n Can it be filled when , But when loading things, you need to start with a big backpack , Because this can keep the last backpack state

The sum must be even , Odd number /2 There is .5 No matter how we find it, we can't find decimals in the integer array

Code

Depth-first search

/*
*int findTargetSumWays(int* nums, int numsSize, int target)
int findTargetSumWays： The number of times that different expression values in the array are equal to the target value 
int* nums： Array 
int numsSize： The length of the array 
int target: The target 
 Return value ： Number of valid expressions 
*/
int dfs(int * nums, int inode, int numsSize, int sum, int target)
{
    if(inode == numsSize){// Enumerate to the last element 
        if(sum == target){// Valid expressions , Meet the requirements of the topic 
            return 1;
        }
        else{// dissatisfaction 
            return 0;
        }
    }
    return dfs(nums, inode+1, numsSize, sum+nums[inode], target) + dfs(nums, inode+1, numsSize, sum-nums[inode], target);// Add up all the cases 
}
int findTargetSumWays(int* nums, int numsSize, int target){
    return dfs(nums, 0, numsSize, 0, target);// Depth first search enumerates all elements 
}

 author ：xun-ge-v
 link ：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Dynamic programming , Convert to 0 1 knapsack problem

/*
*int findTargetSumWays(int* nums, int numsSize, int target)
int findTargetSumWays： The number of times that different expression values in the array are equal to the target value 
int* nums： Array 
int numsSize： The length of the array 
int target: The target 
 Return value ： Number of valid expressions 
*/
int findTargetSumWays(int* nums, int numsSize, int target){
    int sum = 0;
    for(int i = 0; i < numsSize; i++)// Sum up 
    {
        sum += nums[i];
    } 
    int diff = sum-target;
    if(diff < 0 || diff % 2 != 0)// A special case 
    {
        return 0;
    }
    int n = diff/2;
    int dp[n+1];
    memset(dp, 0, sizeof(int) * (n + 1));
    dp[0] = 1;
    for(int i = 0; i < numsSize; i++)// Enumerate things 
    {
        for(int j = n; j >= nums[i]; j--)// Update your backpack 
        {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[n];
}


 author ：xun-ge-v
 link ：https://leetcode.cn/problems/target-sum/solution/by-xun-ge-v-gmb5/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Time and space complexity