Medium

题目描述

给你一个整数数组 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

解题思路

这道题有两种主要解法：回溯法和动态规划。

方法一：回溯法（暴力枚举） 对每个数字选择加号或减号，递归枚举所有可能的组合。当遍历完所有数字时，检查当前和是否等于目标值。

方法二：动态规划（推荐） 这是一个经典的转换问题。假设加正号的数字和为P，加负号的数字和为N，那么：

  • P + N = sum（数组总和）
  • P - N = target
  • 解得：P = (sum + target) / 2

问题转化为：从数组中选择一些数字，使其和等于P的方案数。这就是经典的"背包问题"。

使用一维DP数组：dp[i] 表示和为i的方案数。状态转移方程为：dp[j] += dp[j - num]

需要注意边界条件：

  1. 如果 (sum + target) 为奇数，无解
  2. 如果 target > sum 或 target < -sum，无解

代码实现

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        if (target > sum || target < -sum || (sum + target) % 2 == 1) {
            return 0;
        }
        
        int targetSum = (sum + target) / 2;
        vector<int> dp(targetSum + 1, 0);
        dp[0] = 1;
        
        for (int num : nums) {
            for (int j = targetSum; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[targetSum];
    }
};

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        
        if target > total or target < -total or (total + target) % 2 == 1:
            return 0
        
        target_sum = (total + target) // 2
        dp = [0] * (target_sum + 1)
        dp[0] = 1
        
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]
        
        return dp[target_sum]

public class Solution {
    public int FindTargetSumWays(int[] nums, int target) {
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        
        if (target > sum || target < -sum || (sum + target) % 2 == 1) {
            return 0;
        }
        
        int targetSum = (sum + target) / 2;
        int[] dp = new int[targetSum + 1];
        dp[0] = 1;
        
        foreach (int num in nums) {
            for (int j = targetSum; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[targetSum];
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((a, b) => a + b, 0);
    
    if (Math.abs(target) > sum || (sum + target) % 2 === 1) {
        return 0;
    }
    
    const subsetSum = (sum + target) / 2;
    const dp = new Array(subsetSum + 1).fill(0);
    dp[0] = 1;
    
    for (const num of nums) {
        for (let j = subsetSum; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    
    return dp[subsetSum];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
回溯法O(2^n)O(n)
动态规划O(n × sum)O(sum)

其中 n 是数组长度，sum 是数组元素总和。动态规划解法明显更优，推荐使用。

相关题目