494. Target Sum

LeetCode 494. Target Sum

Description

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

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be 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

Constraints:

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• 0 <= sum(nums[i]) <= 1000

• -1000 <= target <= 1000

Tags

Dynamic Programming, Depth-first Search

Solution

We denote sum as the sum of nums, and neg as the sum of all elements whose sign is -. Then we can obtain $(sum−neg)−neg=sum−2⋅neg=target$ , then we obtain $neg=(sum−target)/2$ . Now our goal is to find a subset of nums whose sum is neg.

We use Dynamic Programming strategy and build a 2D-array dp, and dp[i][j] represents the number of combination of some of elements in nums[:i] whose sum is j.

• If num[i]>j, we will not pick it, and dp[i][j]=dp[i-1][j];

• Otherwise, if we pick it, we will have extra dp[i-1][j-num[i]] choices, meaning that dp[i][j]=dp[i-1][j]+dp[i-1][j-num[i]].

Finally, the answer is dp[len(nums)][neg].

Complexity

• Time complexity: $O(n\times (sum-target))$

• Space complexity: $O(sum-target)$

Code

func findTargetSumWays(nums []int, target int) int {
	var sum int
	for _, num := range nums {
		sum += num
	}
	diff := sum - target
	if diff < 0 || diff%2 == 1 {
		return 0
	}
	neg := diff / 2
	dp := make([]int, neg+1)
	dp[0] = 1
	for _, num := range nums {
		for j := neg; j >= num; j-- {
			dp[j] += dp[j-num]
		}
	}
	return dp[neg]
}

Reference

1. 目标和