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