LC494.目标和

1. 题目

• 494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

**输入：** nums = [1,1,1,1,1], target = 3
**输出：** 5
**解释：** 一共有 5 种方法让最终目标和为 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

示例 2：

**输入：** nums = [1], target = 1
**输出：** 1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

2. 思路

• 本质上就是把数组分成两个部分，假定第一个部分的总和是 sum1，第二个部分的总和是 sum2，那么 sum1 + sum2 = allSum && sum1 - sum2 = target
• 那么，sum1 的和实际上是一个确切的值，该问题就变成一个 01 背包问题，01背包求方案数。
• 本质：从数组当中挑选一些数字，能够组成一个值。

3. 代码

func findTargetSumWays(nums []int, target int) int {
    // sum1 - sum2 = target
    // sum1 + sum2 = all
    // sum1 = (target + all) / 2

    all := 0
    for _, v := range nums {
        all += v
    }
    if (all + target) % 2 != 0 || (all + target) < 0{
        return 0
    }
    sum1 := (all + target) / 2

    f := make([]int, sum1 + 1)

    // 01 package
    f[0] = 1
    for i := range nums {
        curVol := nums[i]
        for k := sum1; k >= curVol; k-- {
            f[k] = f[k] + f[k - curVol]
        }
    }

    return f[sum1]
}