“This is the 35th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

494. The target and

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], you can add ‘+’ before 2, ‘-‘ before 1, and then concatenate 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

Brute force

Given an array nums with n elements, each of which can be positive or negative, find the number of results that can make the final value equal to the target value

Here we’re brute force cracking all the results for each value that is positive and negative, if it’s equal to target then the total number res plus one

Concrete implementation:

For two cases that require each value, we use a recursive method here. For computed, a recursive function takes three parameters: curr the current value, nums the remaining element, and target the target value

  • The declaration res=0 is used to record the number of possible results
  • Declares a computed recursive function that takes three parameters curr, nums, and target
    • If the length of nums is 0, the recursion ends. If curr===target then res++
    • Deconstruct NUMNS to reassign NUMs, because recursively passing in NUMs, if passing in the same NUMS object will cause data confusion, so we need to deconstruct the clone data
    • Pop an element item as a function of the current processing, and compute curr plus or minus item to get curr1 and curr2, continuing the recursive processing
  • Finally, return res
var findTargetSumWays = function (nums, target) {
    var res = 0
    function computed(curr, nums, target) {
        if (nums.length === 0) {
            if (curr === target) {
                res++
            }

            return
        }
        // Deconstruct the clone data
        nums = [...nums]
        var item = nums.pop()
        var curr1 = curr + item
        var curr2 = curr - item
        computed(curr1, nums, target)
        computed(curr2, nums, target)
    }
    computed(0, nums, target)
    return res
};
Copy the code

Thank you. Come on