Luobuyu's Blog

0%

494. 目标和

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.1k 阅读时长 ≈ 2 分钟
01背包方案数。

494. 目标和

题目描述：

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

数据范围：

$1\le nums.len \le 20$

题解：

首先，假设减去的为 $x$ ，则 $sum - x - x = target$ ，可以得出 $x = \frac{sum - target}{2}$ 。也就是需要从数组中选出一部分数，而且这部分数的和为 $x$ 。可以使用01背包解决。

但是该问题需要求方案数，假设 $dp[i][j]$ 为前 $i$ 中取出一部分数和为 $j$ 的方案数，则对于 $nums[i]$ 如果不取，则 $dp[i][j] = dp[i-1][j]$ ，如果取的话 $dp[i][j] = dp[i-1][j-nums[i]]$ ，总的方案数为二者加起来。可以直接使用一维，只递推就行。

也可以使用dfs回溯解决。

代码：

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int backpack(vector<int> &nums, int size)
    {
        // dp[i][j] = (dp[i-1][j], dp[i-1][j - size[i]])
        vector<int> dp(size + 1);
        dp[0] = 1;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = size; j >= nums[i]; --j)
            {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[size];
    }
    int findTargetSumWays(vector<int> &nums, int target)
    {
        // sum - 2x = target, x = (sum-target)/2
        int sum = 0;
        for (auto &x : nums)
            sum += x;
        if ((sum - target) & 1)
            return 0;
        return backpack(nums, (sum - target) / 2);
    }
};
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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int findTargetSumWays(vector<int> &nums, int target)
    {
        // sum - 2x = target, x = (sum-target)/2
        int sum = 0;
        for (auto &x : nums)
            sum += x;
        if ((sum - target) < 0 || (sum - target) & 1)
            return 0;
        return dfs(nums, target, sum, 0, 0);
    }
    int dfs(vector<int> &nums, int target, int extra, int sum, int step)
    {
        if(sum + extra < target || sum - extra > target)
            return 0;
        if (step >= nums.size())
        {
            if (sum == target)
                return 1;
            else
                return 0;
        }

        int ans = 0;
        ans += dfs(nums, target, extra - nums[step], sum + nums[step], step + 1);
        ans += dfs(nums, target, extra - nums[step], sum - nums[step], step + 1);
        return ans;
    }
};