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

解法一：动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func findTargetSumWays(nums []int, target int) int {
    n := len(nums)
    dp := make([][2001]int, n)
    dp[0][1000-nums[0]] = 1
    dp[0][1000+nums[0]] = 1
    if nums[0] == -nums[0] {
        // 处理 nums[0] == 0 的情况
        dp[0][1000] = 2
    }
    for i := 1; i < n; i++ {
        for j := 0; j < 2001; j++ {
            if dp[i-1][j] != 0 {
                dp[i][j+nums[i]] += dp[i-1][j]
                dp[i][j-nums[i]] += dp[i-1][j]
            }
        }
    }
    return dp[n-1][1000+target]
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    diff := sum - target
    if diff < 0 || diff%2 == 1 {
        return 0
    }
    neg := diff / 2
    dp := make([]int, neg+1)
    dp[0] = 1
    for _, num := range nums {
        for j := neg; j >= num; j-- {
            dp[j] += dp[j-num]
        }
    }
    return dp[neg]
}

解法二：回溯

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func findTargetSumWays(nums []int, target int) int {
    n, ans := len(nums), 0
    var backtracking func(idx, val int)
    backtracking = func(idx, val int) {
        if idx >= n {
            if target == val {
                ans++
            }
            return
        }
        backtracking(idx+1, val-nums[idx])
        backtracking(idx+1, val+nums[idx])
    }
    backtracking(0, 0)
    return ans
}