目标和

1. 题目描述

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

2. 思路

1. 思路一
   • DFS
   • 本质上和组合总和.md一样
   • 区别在于可加可减

3. 实现

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
    }
    //正数，用+
    findTargetSumWaysDFS(nums, index+1, S-nums[index], count)
    //负数，用-
    findTargetSumWaysDFS(nums, index+1, S+nums[index], count)
    //以上代码等同如下：
    //for _, multi := range []int{1, -1} {
	//	sum -= multi * nums[index]
	//	findTargetSumWaysDFS(nums, index+1, sum, count)
	//	sum += multi * nums[index]
	//}
}

4. 参考

• 494. 目标和 - 力扣（LeetCode）