Target Sum

Problem Statement

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

For each number in the array, you can choose to either add or subtract it to a total sum.

• For example, if nums = [1, 2], one possible sum would be "+1-2=-1".

If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: "+1-1" and "-1+1".

Return the number of different ways that you can build the expression such that the total sum equals target.

Example 1:

Input: nums = [2,2,2], target = 2

Output: 3

Explanation: There are 3 different ways to sum the input numbers to get a sum of 2. +2 +2 -2 = 2 +2 -2 +2 = 2 -2 +2 +2 = 2

Constraints:

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

Recommended Time and Space Complexity

You should aim for a solution with O(n * m) time and O(m) space, where n is the length of the array nums and m is the sum of all the elements in the array.

Solution

Recursion

def find_target_sum_ways(nums: List[int], target: int) -> int:
    def backtrack(i, total):
        if i == len(nums):
            return 1 if total == target else 0

        return (backtrack(i + 1, total + nums[i]) +
                backtrack(i + 1, total - nums[i]))

    return backtrack(0, 0)

Time complexity: O(2 ^ n) Space complexity: O(n)