Topic Description:
You are given an integer array nums and an integer target.
We can construct an expression by adding a ‘+’ or ‘-‘ to each integer in an array, and then concatenating all the integers:
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 using the above method, where the result of the operation is equal to target.
Â
Example 1:
Input: nums = [1,1,1,1,1,1], target = 3 output: 5 explanation: there are five ways to make the final target sum 3.
Minus 1 plus 1 plus 1 plus 1 plus 1 is 3
Plus 1 minus 1 plus 1 plus 1 plus 1 is 3
Plus 1 plus 1 minus 1 plus 1 plus 1 is 3
Plus 1 plus 1 plus 1 minus 1 plus 1 is 3
+1 +1 +1 +1 = 1
Nums = [1], target = 1 Output: 1
Tip:
1 <= nums.length <= 20 0 <= nums[i] <= 1000 0 <= sum(nums[i]) <= 1000 -1000 <= target <= 1000
Source: LeetCode link: leetcode-cn.com/problems/ta… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.
Their thinking
01 backpack 🎒 problem conversion:
01 backpack
The nums array element must be + or -. The nums array element must be + or -.
- W: No. 01 backpack.
- Suppose the sum of all the elements whose symbol is + is x; The absolute value of the sum of all the elements of sign – is y;
- The result we want is target=x-y;
- And we know that the sum of x and y is the sum of the array sum=x+y;
- From the above two formulas, x=(target+sum)/2
- Convert the problem to pick a few numbers in NUMS whose sum is x;
- Full issue: 01 knapsack with capacity x and items in nums array 🎒 issue;
Dynamic programming tetralogy:
- Determine the meaning of DP
- Dp [j] = dp[j] = dp[j] = dp[j]
- Dp [j] = dp[j] + dp[j-num],
- Dp array initialization:
- Initialize the DP array with capacity x to 0;
- And dp [0] = 1; What it actually means: There are only 1 methods to fill a backpack with capacity 0;
- Traversal order:
- 01 backpack must be the outer for loop traversing items, the inner for loop traversing backpack capacity and traversing from back to front!
Space-time complexity
- Time complexity: O(n * x) two-layer for loop; N for the nums. Length;
- Space complexity: O(x))
code
/ * * *@param {number[]} nums
* @param {number} target
* @return {number}* /
var findTargetSumWays = function(nums, target) {
let sum=0;
for(let num of nums){
sum+=num
}
// When the target value is greater than the maximum value of the array elements, that is, when all elements are selected +;
if(target>sum){
return 0;
}
// If x is not an integer, that is, (target+sum) is not even;
if((target+sum)%2= =1) {return 0;
}
//dp [j] = dp[j] = dp[j] = dp[j]
// Max capacity x
let x=Math.floor((target+sum)/2);
// dp is initialized; Dp [0]=1;
let dp=new Array(x+1).fill(0);
dp[0] =1;
Dp [j]=dp[j]+dp[j-nums[I]]
for(let num of nums){
for(letj=x; j>=num; j--){ dp[j]=dp[j]+dp[j-num] } }// end of for
return dp[x]
};
Copy the code