494.目标和 (Medium)*

题目描述*

给定一个非负整数数组，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

注意*

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

代码*

是在 dfs 下遇到的，使用 dfs 穷举所有可能最多 $2^{20}$ 。虽然没超时，但是还是太慢了。

此问题可以转换为 01 背包问题，经过以下可以转换为 Subset Sum 问题，将数组看成两部分 P 和 N 表示正负号：

$\begin{aligned} \rm sum(P) - sum(N) & = \rm target \\ \rm sum(P) + sum(N) + sum(P) - sum(N) & = \rm target + sum(P) + sum(N) \\ \rm 2 \times sum(P) & = \rm target + sum(nums) \end{aligned}$

问题转换成了求和为 (target + sum(nums))/2 的子集合，使用动态规划。

dfs01 背包

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return dfs(nums, S, 0);
    }
    int dfs(vector<int>& nums, unsigned int target, int start) {
        if(target == 0 && start == nums.size()) {
            return 1;
        }
        if(start >= nums.size()) {
            return 0;
        }
        int res = 0;
        res += dfs(nums, target + nums[start], start + 1);
        res += dfs(nums, target - nums[start], start + 1);
        return res;
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = 0;
        for(auto& i : nums) {
            sum += i;
        }
        if((S + sum) & 1 || S > sum) {
            return 0;
        }
        int curTarget = (S + sum) / 2;
        vector<int> dp(curTarget + 1, 0);
        dp[0] = 1;
        for(auto i : nums) {
            for(int j = curTarget; j >= i; j--) {
                dp[j] = dp[j] + dp[j - i];
            }
        }
        return dp[curTarget];
    }
};

最后更新: July 23, 2022