494. Target Sum

Problem

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Problem Statement

Given a non-negative integer array, a1, a2, ..., an, and a target number, S. Now there are two symbols + and -. For any integer in the array, you can choose one symbol from + or - to add in front of it. Return the number of all ways to add symbols that can make the final array sum equal to the target number S.

Notes:

The array is non-empty, and its length will not exceed 20.
The sum of the initial array will not exceed 1000.
It is guaranteed that the final returned result can be stored in a 32-bit integer.

Solution Thought Process

Given an array, it is required to add a + or - sign in front of each element in this array, so that the final total sum equals S. Ask how many different ways there are.
This problem can be solved with DP and DFS. The DFS method is relatively brute-force and simple. See the code. Here, let's analyze the DP approach. The problem requires adding a + or - sign in front of array elements, which is actually equivalent to dividing the array into 2 groups: one group all with + signs, and one group all with - signs. Let the group with + signs be P, and the group with - signs be N, then the following relationship can be derived.
go
```
sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                       2 * sum(P) = target + sum(nums)
```
Add sum(N) + sum(P) to both sides of the equation, and then the result 2 * sum(P) = target + sum(nums) can be obtained. Then this problem is converted into whether such a set can be found in the array whose sum equals (target + sum(nums)) / 2. Then this problem is transformed into Problem 416. What is stored in dp[i] is the number of ways to make the sum equal to i.
If the sum is not even, that is, it cannot be divided by 2, then it means no solution satisfying the problem requirements can be found, so directly output 0.

Code


func findTargetSumWays(nums []int, S int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	if S > total || (S+total)%2 == 1 {
		return 0
	}
	target := (S + total) / 2
	dp := make([]int, target+1)
	dp[0] = 1
	for _, n := range nums {
		for i := target; i >= n; i-- {
			dp[i] += dp[i-n]
		}
	}
	return dp[target]
}

// Solution 2: DFS
func findTargetSumWays1(nums []int, S int) int {
	// sums[i] stores the suffix sum nums[i:], i.e., the sum from i to the end
	sums := make([]int, len(nums))
	sums[len(nums)-1] = nums[len(nums)-1]
	for i := len(nums) - 2; i > -1; i-- {
		sums[i] = sums[i+1] + nums[i]
	}
	res := 0
	dfsFindTargetSumWays(nums, 0, 0, S, &res, sums)
	return res
}

func dfsFindTargetSumWays(nums []int, index int, curSum int, S int, res *int, sums []int) {
	if index == len(nums) {
		if curSum == S {
			*(res) = *(res) + 1
		}
		return
	}
	// Pruning optimization: if the value of sums[index] is less than the remaining value needed to be positive, then even if all the remaining signs are +, it will not help, so we can prune here
	if S-curSum > sums[index] {
		return
	}
	dfsFindTargetSumWays(nums, index+1, curSum+nums[index], S, res, sums)
	dfsFindTargetSumWays(nums, index+1, curSum-nums[index], S, res, sums)
}