494. 目标和 (opens new window)

Description

Difficulty: 中等

Related Topics: 数组 (opens new window), 动态规划 (opens new window), 回溯 (opens new window)

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

Solution

Language: JavaScript

/**
 * 
 * 
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
    let sum = 0;
    for (let num of nums) {
        sum += num;
    }

    // S大于sum，不可能实现，返回0
    if (S > sum) {
        return 0;
    }
    
    // 如果S + sum不是偶数，不可能实现，返回0
    if ((S + sum) % 2 == 1) {
        return 0;
    }

    let target = Math.floor((S + sum) / 2);
    let dp = Array(target + 1).fill(0);
    dp[0] = 1;

    for (let num of nums) {
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] + dp[j - num];
        }
    }

    return dp[target];
};

回溯算法其实就是一种暴力穷举解法

对于每个数字 nums[i]，我们可以选择给一个正号 + 或者一个负号 -

var findTargetSumWays = function(nums, S) {
    // 方法1：深度遍历
    let count = 0;
    function dfs(i, res) {
        if(i === nums.length) {
            if(res === S) {
                count++;
            }
            return;
        };
        dfs(i+1, res+nums[i]);
        dfs(i+1, res-nums[i]);
    }
    dfs(1, nums[0]);
    dfs(1, -nums[0]);
    return count;
};