Practice/Meta/Leetcode 494. Target Sum

Leetcode 494. Target Sum

CodingMust

Problem

You are given an array of integers nums and an integer target. Your task is to build an expression by placing either a + (plus) or - (minus) operator before each number in the array. The expression should evaluate to the target value.

Return the number of different expressions you can build that evaluate to target.

Requirements

1. Place either + or - before each element in nums
2. Calculate all possible ways to reach the target sum
3. Return the total count of valid expressions
4. All numbers in nums must be used exactly once

Constraints

• 1 ≤ nums.length ≤ 20
• 0 ≤ nums[i] ≤ 1000
• 0 ≤ sum(nums[i]) ≤ 1000
• -1000 ≤ target ≤ 1000
• Time complexity should be O(n × sum) where n is the length of nums
• Space complexity should be O(sum) or better

Examples

Example 1:

` Input: nums = [1, 1, 1, 1, 1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to reach target 3:

• +1 + 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 = 3 `

Example 2:

Input: nums = [1], target = 1 Output: 1 Explanation: Only one way: +1 = 1

Example 3:

` Input: nums = [1, 2, 3], target = 0 Output: 2 Explanation: Two ways:

• +1 + 2 - 3 = 0
• +1 - 2 - 3 + 4... wait, we only have [1,2,3] Actually: -1 - 2 + 3 = 0 and +1 + 2 - 3 = 0 `