Target Sum

1. Problem Description

Given an array of non-negative integers, a1, a2, …, an, and a target number S. You now have two symbols, + and -. For every integer in the array, you may choose either + or - and place it in front of the number.

Return the number of ways to assign signs so that the final array sum equals the target S.

2. Approach

1. Approach 1
   • DFS
   • Essentially the same as Combination Sum
   • The difference is that each number can be added or subtracted

3. Implementation

3.1. DFS

func findTargetSumWays(nums []int, S int) int {
    count := 0

    findTargetSumWaysDFS(nums, 0, S, &count)

    return count
}

func findTargetSumWaysDFS(nums []int, index int, S int, count *int) {
    if index == len(nums) {
        if S==0 {
            (*count)++
        }
        return
    }
    // Positive sign: use +
    findTargetSumWaysDFS(nums, index+1, S-nums[index], count)
    // Negative sign: use -
    findTargetSumWaysDFS(nums, index+1, S+nums[index], count)
    // The code above is equivalent to the following:
    //for _, multi := range []int{1, -1} {
	//	sum -= multi * nums[index]
	//	findTargetSumWaysDFS(nums, index+1, sum, count)
	//	sum += multi * nums[index]
	//}
}

4. References

• 494. Target Sum - LeetCode