Target Sum

Medium

The problem

Put a + or a - in front of every number in nums, then add them all up. Return how many different ways of choosing the signs give a total of exactly target.

Example 1
Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Exactly one of the five 1s gets a minus sign, and there are 5 choices for which one: -1+1+1+1+1 = 3, and so on.
Example 2
Input: nums = [1], target = 1
Output: 1
Only +1 works.

Limits

1 ≤ len(nums) ≤ 20
0 ≤ nums[i] ≤ 1,000
The total of all numbers is at most 1,000
-1,000 ≤ target ≤ 1,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Choosing + or − for every number splits the numbers into two groups. What must one group sum to?

The idea

Either memoize (index, total) or convert to "count subsets with sum (S + target)/2" using a 1-D knapsack count.

Target: O(n · sum) time

Go function shape

func findTargetSumWays(nums []int, target int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// FindTargetSumWays: choose + or - for every number so the total is target.
// The + group P and - group N satisfy P - N = target and P + N = sum, so P = (sum + target) / 2:
// count subsets that add up to P.
func FindTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, n := range nums {
		sum += n
	}
	if (sum+target)%2 != 0 || sum+target < 0 || target > sum || -target > sum {
		return 0
	}
	want := (sum + target) / 2
	ways := make([]int, want+1)
	ways[0] = 1
	for _, n := range nums {
		for s := want; s >= n; s-- { // descending: each number used at most once
			ways[s] += ways[s-n]
		}
	}
	return ways[want]
}

Read the lesson: 2-D Dynamic Programming