“This is my 32nd day of participating in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

You are given an integer array nums and an integer target.

We can construct an expression by adding a ‘+’ or a ‘-‘ to each integer in the array and then concatenating all integers:

  • For example,nums = [2, 1], can be in2Before you add'+'In the1Before you addThe '-'And then we connect them together to get the expression"+ 2-1" 。

Returns the number of different expressions equal to target that can be constructed using the above method.

Example 1:

Input: nums = [1,1,1,1,1], target = 3 output: 5 explanation: there are 5 ways to make the final target sum equal to 3. -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 = 3Copy the code

Example 2:

Input: nums = [1], target = 1 Output: 1Copy the code

Tip:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Their thinking

At first glance, this problem may seem a bit complicated. Each number has two possibilities, four possibilities for two numbers and eight possibilities for three numbers, and the result is equal to the number of different expressions for target,emmmm…. Actually we can see the problem from a different Angle, when only a number, we are sure you can get the result of the two expressions, and x – x, then, for the next number is nothing more than two possible, positive or negative, so we have a a number of the past, you can get in front of all the possible results of digital combination, Finally, all numbers are obtained using the number of expressions that can be obtained with a result value of target. This is obviously a problem of derivation, so we can do it with dynamic programming. State definition: According to the above analysis results, there are two variables, using the number of numbers and the result value that can be obtained, so we define two-dimensional dp dp[I][j] to represent the number of expressions of j that can be obtained from the first I numbers. Transfer equation: Since there are only two possibilities for each number, positive or negative, dp[I][j] can be obtained from the combination of the former i-1 number j-x, or from the combination of the former i-1 number j+x, where x is the value of the ith number, So we get dp[I][j] = DP [i-1][j-x]+ DP [i-1][j+x]. With the state definition and transition equation in hand, it’s time to implement the code! 💪

Code implementation

Var findTargetSumWays = function (nums, target) {const len = nums.length, Let total = 0 for (let I = 0; i < len; I ++) total += nums[I] // For (let I = 0; i <= len; Dp [0][0] = 1 dp[0][total] = 1 dp[0][total] = 1 Find each layer dp for (let I = 1; i <= len; Const x = nums[i-1] const x = nums[i-1] sum += x for (let j = -sum; j <= sum; J ++) {// every dp in the range // Note here that j-x and j+x may exceed the subscript of our array, So arithmetic to | | 0 dp + total [j] [I] = [dp] [I - 1 [j - x + total] | | 0) + (dp] [I - 1 + x + total [j] | | 0)}} / / return all the Numbers are used, Get the / / the number of expressions in the target in the same way, because the target + total may be beyond the dp array subscript, take out return 0 dp [len] [target + total] | | 0}Copy the code

At this point we are done with leetcode-494-target sum

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻