参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 494.目标和

力扣题目链接 (opens new window)

难度：中等

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5

解释：

-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

一共有5种方法让最终目标和为3。

提示：

数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

# 算法公开课

《代码随想录》算法视频公开课 (opens new window)：装满背包有多少种方法？| LeetCode：494.目标和 (opens new window)，相信结合视频再看本篇题解，更有助于大家对本题的理解。

# 思路

如果对背包问题不都熟悉先看这两篇：

如果跟着「代码随想录」一起学过回溯算法系列 (opens new window)的录友，看到这道题，应该有一种直觉，就是感觉好像回溯法可以暴搜出来。

事实确实如此，下面我也会给出相应的代码，只不过会超时。

这道题目咋眼一看和动态规划背包啥的也没啥关系。

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

# 回溯算法

在回溯算法系列中，一起学过这道题目回溯算法：39. 组合总和 (opens new window)的录友应该感觉很熟悉，这不就是组合总和问题么？

此时可以套组合总和的回溯法代码，几乎不用改动。

当然，也可以转变成序列区间选+ 或者 -，使用回溯法，那就是另一个解法。

我也把代码给出来吧，大家可以了解一下，回溯的解法，以下是本题转变为组合总和问题的回溯法代码：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (S > sum) return 0; // 此时没有方案
        if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要格外小心数值溢出的问题
        int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和

        // 以下为回溯法代码
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 需要排序
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

当然以上代码超时了。

也可以使用记忆化回溯，但这里我就不在回溯上下功夫了，直接看动规吧

# 动态规划（二维dp数组）

假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，用nums装满容量为x的背包，有几种方法。

这里的x，就是bagSize，也就是我们后面要求的背包容量。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了，例如sum是5，target是2 的话其实就是无解的，所以：

（C++代码中，输入的S 就是题目描述的 target）
if ((target + sum) % 2 == 1) return 0; // 此时没有方案

1
2

同时如果target 的绝对值已经大于sum，那么也是没有方案的。

if (abs(target) > sum) return 0; // 此时没有方案

因为每个物品（题目中的1）只用一次！

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

确定dp数组以及下标的含义

先用二维 dp数组求解本题，dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

01背包为什么这么定义dp数组，我在0-1背包理论基础 (opens new window)中确定dp数组的含义里讲解过。

确定递推公式

我们先手动推导一下，这个二维数组里面的数值。

先只考虑物品0，如图：

（这里的所有物品，都是题目中的数字1）。

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是1，即放物品0。

装满背包容量为2 的方法个数是0，目前没有办法能装满容量为2的背包。

接下来考虑物品0 和物品1，如图：

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是2，即放物品0 或者放物品1。

装满背包容量为2 的方法个数是1，即放物品0 和放物品1。

其他容量都不能装满，所以方法是0。

接下来考虑物品0 、物品1 和物品2 ，如图：

装满背包容量为0 的方法个数是1，即放0件物品。

装满背包容量为1 的方法个数是3，即放物品0 或者放物品1 或者放物品2。

装满背包容量为2 的方法个数是3，即放物品0 和放物品1、放物品0 和物品2、放物品1 和物品2。

装满背包容量为3的方法个数是1，即放物品0 和物品1 和物品2。

通过以上举例，我们来看 dp[2][2] 可以有哪些方向推出来。

如图红色部分：

dp[2][2] = 3，即放物品0 和放物品1、放物品0 和物品 2、放物品1 和物品2，如图所示，三种方法：

容量为2 的背包，如果不放物品2 有几种方法呢？

有 dp[1][2] 种方法，即背包容量为2，只考虑物品0 和物品1 ，有 dp[1][2] 种方法，如图：

容量为2 的背包，如果放物品2 有几种方法呢？

首先要在背包里先把物品2的容量空出来，装满刨除物品2容量的背包有几种方法呢？

刨除物品2容量后的背包容量为 1。

此时装满背包容量为1 有 dp[1][1] 种方法，即：不放物品2，背包容量为1，只考虑物品 0 和物品 1，有 dp[1][1] 种方法。

如图：

有录友可能疑惑，这里计算的是放满容量为2的背包有几种方法，那物品2去哪了？

在上面图中，你把物品2补上就好，同样是两种方法。

dp[2][2] = 容量为2的背包不放物品2有几种方法 + 容量为2的背包放物品2有几种方法

所以 dp[2][2] = dp[1][2] + dp[1][1] ，如图：

以上过程，抽象化如下：

不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。
放物品i：即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。

本题中，物品i的容量是nums[i]，价值也是nums[i]。

递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

考到这个递推公式，我们应该注意到，j - nums[i] 作为数组下标，如果 j - nums[i] 小于零呢？

说明背包容量装不下物品i，所以此时装满背包的方法值等于不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j];

所以递推公式：

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

1
2

dp数组如何初始化

先明确递推的方向，如图，求解 dp[2][2] 是由上方和左上方推出。

那么二维数组的最上行和最左列一定要初始化，这是递推公式推导的基础，如图红色部分：

关于dp[0][0]的值，在上面的递推公式讲解中已经讲过，装满背包容量为0 的方法数量是1，即放0件物品。

那么最上行dp[0][j] 如何初始化呢？

dp[0][j]：只放物品0，把容量为j的背包填满有几种方法。

只有背包容量为物品0 的容量的时候，方法为1，正好装满。

其他情况下，要不是装不满，要不是装不下。

所以初始化：dp[0][nums[0]] = 1 ，其他均为0 。

表格最左列也要初始化，dp[i][0] : 背包容量为0，放物品0 到物品i，装满有几种方法。

都是有一种方法，就是放0件物品。

即 dp[i][0] = 1

但这里有例外，就是如果物品数值就是0呢？

如果有两个物品，物品0为0，物品1为0，装满背包容量为0的方法有几种。

放0件物品
放物品0
放物品1
放物品0 和物品1

此时是有4种方法。

其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。

初始化如下：

int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) numZero++;
    dp[i][0] = (int) pow(2.0, numZero);
}

1
2
3
4
5

确定遍历顺序

在明确递推方向时，我们知道当前值是由上方和左上方推出。

那么我们的遍历顺序一定是从上到下，从左到右。

因为只有这样，我们才能基于之前的数值做推导。

例如下图，如果上方没数值，左上方没数值，就无法推出 dp[2][2]。

那么是先从上到下，再从左到右遍历，例如这样：

for (int i = 1; i < nums.size(); i++) { // 行，遍历物品
    for (int j = 0; j <= bagSize; j++) { // 列，遍历背包
    }
}

1
2
3
4

还是先从左到右，再从上到下呢，例如这样：

for (int j = 0; j <= bagSize; j++) { // 列，遍历背包
    for (int i = 1; i < nums.size(); i++) { // 行，遍历物品
    }
}

1
2
3
4

其实以上两种遍历都可以！（但仅针对二维DP数组是这样的）

这一点我在 01背包理论基础 (opens new window)中的遍历顺序部分讲过。

这里我再画图讲一下，以求dp[2][2]为例，当先从上到下，再从左到右遍历，矩阵是这样：

当先从左到右，再从上到下遍历，矩阵是这样：

这里大家可以看出，无论是以上哪种遍历，都不影响 dp[2][2]的求值，用来推导 dp[2][2] 的数值都在。

举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], target: 3

bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下：

这么大的矩阵，我们是可以自己手动模拟出来的。

在模拟的过程中，既可以帮我们寻找规律，也可以帮我们验证递推公式加遍历顺序是不是按照我们想象的结果推进的。

最后二维dp数组的C++代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(target) > sum) return 0; // 此时没有方案
        if ((target + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (target + sum) / 2;
        
        vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));
        
        // 初始化最上行
        if (nums[0] <= bagSize) dp[0][nums[0]] = 1; 

        // 初始化最左列，最左列其他数值在递推公式中就完成了赋值
        dp[0][0] = 1; 

        int numZero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) numZero++;
            dp[i][0] = (int) pow(2.0, numZero);
        }

        // 以下遍历顺序行列可以颠倒
        for (int i = 1; i < nums.size(); i++) { // 行，遍历物品
            for (int j = 0; j <= bagSize; j++) { // 列，遍历背包
                if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
                else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
            }
        }
        return dp[nums.size() - 1][bagSize];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 动态规划（一维dp数组）

将二维dp数组压缩成一维dp数组，我们在 01背包理论基础（滚动数组） (opens new window) 讲过滚动数组，原理是一样的，即重复利用每一行的数值。

既然是重复利用每一行，就是将二维数组压缩成一行。

dp[i][j] 去掉行的维度，即 dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法。

确定递推公式

二维DP数组递推公式： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

去掉维度i 之后，递推公式：dp[j] = dp[j] + dp[j - nums[i]] ，即：dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

dp数组如何初始化

在上面二维dp数组中，我们讲解过 dp[0][0] 初始为1，这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种，放0件物品。

确定遍历顺序

在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们系统讲过对于01背包问题一维dp的遍历。

遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）。

举例推导dp数组

输入：nums: [1, 1, 1, 1, 1], target: 3

bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

dp数组状态变化如下：

大家可以和二维dp数组的打印结果做一下对比。

一维DP的C++代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(target) > sum) return 0; // 此时没有方案
        if ((target + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (target + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

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

时间复杂度：O(n × m)，n为正数个数，m为背包容量
空间复杂度：O(m)，m为背包容量

# 拓展

关于一维dp数组的递推公式解释，也可以从以下维度来理解。（但还是从二维DP数组到一维DP数组这样更容易理解一些）

确定递推公式

有哪些来源可以推出dp[j]呢？

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]种方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]种方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]种方法凑成容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

# 总结

此时大家应该不禁想起，我们之前讲过的回溯算法：39. 组合总和 (opens new window)是不是应该也可以用dp来做啊？

是可以求的，如果仅仅是求个数的话，就可以用dp，但回溯算法：39. 组合总和 (opens new window)要求的是把所有组合列出来，还是要使用回溯法暴搜的。

本题还是有点难度，理解上从二维DP数组更容易理解，做题上直接用一维DP更简洁一些。

大家可以选择哪种方式自己更容易理解。

在后面得题目中，在求装满背包有几种方法的情况下，递推公式一般为：

dp[j] += dp[j - nums[i]];

我们在讲解完全背包的时候，还会用到这个递推公式！

# 其他语言版本

# Java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];

        //如果target的绝对值大于sum，那么是没有方案的
        if (Math.abs(target) > sum) return 0;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if ((target + sum) % 2 == 1) return 0;

        int bagSize = (target + sum) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
}

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

易于理解的二维数组版本：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {

        // 01背包应用之“有多少种不同的填满背包最大容量的方法“
        // 易于理解的二维数组解法及详细注释

        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        // 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和
        // 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
        if(sum < Math.abs(target)){
            return 0;
        }

        // 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析
        // 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的
        if((sum + target) % 2 != 0) {
            return 0;
        }

        int left = (sum + target) / 2;
        
        // dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
        int[][] dp = new int[nums.length][left + 1];

        // 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
        // 其他情况dp[0][j] = 0
        // java整数数组默认初始值为0
        if (nums[0] <= left) {
            dp[0][nums[0]] = 1;
        }

        // 初始化最左列（dp[i][0])
        // 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
        // n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);

        }

        // 递推公式分析：
        // 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
        // nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
        // 由递推公式可知，先遍历i或j都可
        for(int i = 1; i < nums.length; i++) {
            for(int j = 1; j <= left; j++) {
                if(nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }


        return dp[nums.length - 1][left];
        
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# Python

回溯版

class Solution:


    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])  # 将当前路径的副本添加到结果中
        # 如果 sum + candidates[i] > target，则停止遍历
        for i in range(startIndex, len(candidates)):
            if total + candidates[i] > target:
                break
            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if target > total:
            return 0  # 此时没有方案
        if (target + total) % 2 != 0:
            return 0  # 此时没有方案，两个整数相加时要注意数值溢出的问题
        bagSize = (target + total) // 2  # 转化为组合总和问题，bagSize就是目标和

        # 以下是回溯法代码
        result = []
        nums.sort()  # 需要对nums进行排序
        self.backtracking(nums, bagSize, 0, 0, [], result)
        return len(result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

二维DP

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和

        # 创建二维动态规划数组，行表示选取的元素数量，列表示累加和
        dp = [[0] * (target_sum + 1) for _ in range(len(nums) + 1)]

        # 初始化状态
        dp[0][0] = 1

        # 动态规划过程
        for i in range(1, len(nums) + 1):
            for j in range(target_sum + 1):
                dp[i][j] = dp[i - 1][j]  # 不选取当前元素
                if j >= nums[i - 1]:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]  # 选取当前元素

        return dp[len(nums)][target_sum]  # 返回达到目标和的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

一维DP

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和
        dp = [0] * (target_sum + 1)  # 创建动态规划数组，初始化为0
        dp[0] = 1  # 当目标和为0时，只有一种方案，即什么都不选
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量
        return dp[target_sum]  # 返回达到目标和的方案数

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

# Go

二维dp

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    if math.Abs(float64(target)) > float64(sum) {
        return 0 // 此时没有方案
    }
    if (target + sum) % 2 == 1 {
        return 0 // 此时没有方案
    }
    bagSize := (target + sum) / 2
    
    dp := make([][]int, len(nums))
    for i := range dp {
        dp[i] = make([]int, bagSize + 1)
    }
    
    // 初始化最上行
    if nums[0] <= bagSize {
        dp[0][nums[0]] = 1
    }
    
    // 初始化最左列，最左列其他数值在递推公式中就完成了赋值
    dp[0][0] = 1
    
    var numZero float64
    for i := range nums {
        if nums[i] == 0 {
            numZero++
        }
        dp[i][0] = int(math.Pow(2, numZero))
    }
    
    // 以下遍历顺序行列可以颠倒
    for i := 1; i < len(nums); i++ { // 行，遍历物品
        for j := 0; j <= bagSize; j++ { // 列，遍历背包
            if nums[i] > j {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
            }
        }
    }
    return dp[len(nums)-1][bagSize]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

一维dp

func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if abs(target) > sum {
		return 0
	}
	if (sum+target)%2 == 1 {
		return 0
	}
	// 计算背包大小
	bag := (sum + target) / 2
	// 定义dp数组
	dp := make([]int, bag+1)
	// 初始化
	dp[0] = 1
	// 遍历顺序
	for i := 0; i < len(nums); i++ {
		for j := bag; j >= nums[i]; j-- {
			//推导公式
			dp[j] += dp[j-nums[i]]
			//fmt.Println(dp)
		}
	}
	return dp[bag]
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# Javascript

const findTargetSumWays = (nums, target) => {

    const sum = nums.reduce((a, b) => a+b);
    
    if(Math.abs(target) > sum) {
        return 0;
    }

    if((target + sum) % 2) {
        return 0;
    }

    const halfSum = (target + sum) / 2;

    let dp = new Array(halfSum+1).fill(0);
    dp[0] = 1;

    for(let i = 0; i < nums.length; i++) {
        for(let j = halfSum; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }

    return dp[halfSum];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# TypeScript

function findTargetSumWays(nums: number[], target: number): number {
    // 把数组分成两个组合left, right.left + right = sum, left - right = target.
    const sum: number = nums.reduce((a: number, b: number): number => a + b);
    if ((sum + target) % 2 || Math.abs(target) > sum)  return 0;
    const left: number = (sum + target) / 2;
    
    // 将问题转化为装满容量为left的背包有多少种方法
    // dp[i]表示装满容量为i的背包有多少种方法
    const dp: number[] = new Array(left + 1).fill(0);
    dp[0] = 1;  // 装满容量为0的背包有1种方法（什么也不装）
    for (let i: number = 0; i < nums.length; i++) {
        for (let j: number = left; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[left];
};

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

# Scala

object Solution {
  def findTargetSumWays(nums: Array[Int], target: Int): Int = {
    var sum = nums.sum
    if (math.abs(target) > sum) return 0 // 此时没有方案
    if ((sum + target) % 2 == 1) return 0 // 此时没有方案
    var bagSize = (sum + target) / 2
    var dp = new Array[Int](bagSize + 1)
    dp(0) = 1
    for (i <- 0 until nums.length; j <- bagSize to nums(i) by -1) {
      dp(j) += dp(j - nums(i))
    }

    dp(bagSize)
  }
}

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

# Rust

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        let sum = nums.iter().sum::<i32>();
        if target.abs() > sum {
            return 0;
        }
        if (target + sum) % 2 == 1 {
            return 0;
        }
        let size = (sum + target) as usize / 2;
        let mut dp = vec![0; size + 1];
        dp[0] = 1;
        for n in nums {
            for s in (n as usize..=size).rev() {
                dp[s] += dp[s - n as usize];
            }
        }
        dp[size]
    }
}

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

# C

int getSum(int * nums, int numsSize){
    int sum = 0;
    for(int i = 0; i < numsSize; i++){
        sum += nums[i];
    }
    return sum;
}

int findTargetSumWays(int* nums, int numsSize, int target) {
    int sum = getSum(nums, numsSize);
    int diff = sum - target;
    // 两种情况不满足
    if(diff < 0 || diff % 2 != 0){
        return 0;
    }
    int bagSize = diff / 2;
    int dp[numsSize + 1][bagSize + 1];
    dp[0][0] = 1;
    for(int i = 1; i <= numsSize; i++){
        int num = nums[i - 1];
        for(int j = 0; j <= bagSize; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= num){
                dp[i][j] += dp[i - 1][j - num];
            }
        }
    }
    return dp[numsSize][bagSize];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# C#

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

← 15. 动规周总结 17. 一和零 →

# 494.目标和

# 算法公开课

# 思路

# 回溯算法

# 动态规划 （二维dp数组）

# 动态规划 （一维dp数组）

# 拓展

# 总结

# 其他语言版本

# Java

# Python

# Go

# Javascript

# TypeScript

# Scala

# Rust

# C

# C#

# 动态规划（二维dp数组）

# 动态规划（一维dp数组）