题目描述

给定一个非负整数序列，a_1, a_2, ..., a_n，和一个目标值 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 位整数存下。

算法

(动态规划) $O(n \cdot sum)$

1. 定义 $f(i, j)$ 表示添加了前 $i$ 个数字的符号，得到总和为 $j$ 的方案数。
2. 对于第 $i$ 个符号，$f(i, j) = f(i - 1, j + nums[i]) + f(i - 1, j - nums[i])$。
3. $j$ 的范围是 $[-sum, sum]$，$sum$ 为数组元素的总和。
4. 初始值 $f(0, 0) = 1$，最终答案为 $f(n, S)$。
5. 为了方便，第一维的下标从 1 开始；第二维也需要给 $sum$ 的偏移量防止负下标。

时间复杂度

• 状态数为 $O(n \cdot sum)$，转移数和转移时间为 $O(1)$，故总时间复杂度为 $O(n \cdot sum)$。

空间复杂度

• 需要额外 $O(n \cdot sum)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (!(-sum <= S && S <= sum))
            return 0;

        vector<vector<int>> f(n + 1, vector<int>(2 * sum + 1, 0));
        f[0][0 + sum] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = -sum; j <= sum; j++) {
                if (-sum <= j - nums[i - 1])
                    f[i][j + sum] += f[i - 1][j - nums[i - 1] + sum];
                if (j + nums[i - 1] <= sum)
                    f[i][j + sum] += f[i - 1][j + nums[i - 1] + sum];
            }

        return f[n][S + sum];
    }
};