目标和 - Stellar Observer Protocol

608 字

3 分钟

目标和

2025-08-06

Algorithms

动态规划

/

回溯

/

数组

题目描述#

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

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

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

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

解题思路#

DFS回溯：递归遍历数组，对每个数字选择 + 或 -。
终止条件：遍历完数组时，若当前和 == target，计数 +1。
剪枝优化：记录剩余数字和，若剩余和 < 目标差 则提前返回。

关键洞察#

数学转换：问题等价于将数组拆分为两个子集，使两子集和之差为 target。
状态复用：动态规划中，dp[j] 表示和为 j 的方案数，避免重复计算。
偏移处理：负数和时需用偏移量转换下标，确保 DP 数组有效。

复杂度分析#

时间复杂度：
- 回溯：O(2ⁿ)（最坏）
- DP：O(n·range)，range = sum(nums)
空间复杂度：
- 回溯：O(n)（递归栈）
- DP：O(range)

代码实现#

1
/**
2
 * 回溯法
3
 * @param {number[]} nums
4
 * @param {number} target
5
 * @return {number}
6
 */
7
var findTargetSumWays = function (nums, target) {
8
    let res = 0;
9
    const dfs = (i, sum) => {
10
        if (i === nums.length) {
11
            if (sum === target) {
12
                res++;
13
            }
14
            return;
15
        }
16
        dfs(i + 1, sum + nums[i]);
17
        dfs(i + 1, sum - nums[i]);
18
    }
19
    dfs(0, 0);
20
    return res;
21
};

1
/**
2
 * DP
3
 * @param {number[]} nums
4
 * @param {number} target
5
 * @return {number}
6
 */
7
var findTargetSumWays = function(nums, target) {
8
    let sum = 0;
9
    for (const num of nums) {
10
        sum += num;
11
    }
12
    const diff = sum - target;
13
    if (diff < 0 || diff % 2 !== 0) {
14
        return 0;
15
    }
16
    const n = nums.length, neg = diff / 2;
17
    const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0));
18
    dp[0][0] = 1;
19
    for (let i = 1; i <= n; i++) {
20
        const num = nums[i - 1];
21
        for (let j = 0; j <= neg; j++) {
22
            dp[i][j] = dp[i - 1][j];
23
            if (j >= num) {
24
                dp[i][j] += dp[i - 1][j - num];
25
            }
26
        }
27
    }
28
    return dp[n][neg];
29
};