好久没更博客了QAQ。

目标和

题目描述

今天打卡LeetCode看到了一道题目，感觉蛮有趣的。

给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 100

基础解法

这种题目可以简单的暴力回溯解决，思路就不说了。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int r = 0;
        back_track(nums, target, 0, 0, r);
        return r;
    }

    void back_track(vector<int>& nums, int target, int i, int cur, int& r)
    {
        if(i == nums.size())
        {
            if(cur == target)
            {
                ++r;
            }
            return;
        }
        back_track(nums, target, i + 1, cur + nums[i], r);
        back_track(nums, target, i + 1, cur - nums[i], r);
    }
};

进阶解法

如果只是用回溯我也不会写这个博客，下面分享下我的一些思路。

题目中的 \(nums[i]\) 可以看作数值，通过 \(+\) 和 \(-\) 指定其正负，让这些正负数和为 \(target\)。

基于以上分析，很自然的把 \(nums[i]\) 分为两堆，即正堆和 \((P)\) 和负堆和 \((-N)\)，这里 \(0\) 不影响最终结果。

明显根据定义有 \(nums\) 的和 \(S\) 满足 \[ P + N = S \] 要满足题意 \[ P + (-N) = P - N = target \] 相加化简得 \[ P = \frac{S + target}{2} \] 因此等价于在 \(num\) 中选取若干元素，满足这些元素相加为 \(\frac{S + target}{2}\)，求这样的选取方式有多少种。

代码很容易写，注意点小细节即可。

注意就算 \(nums\) 中有负数也不影响最终结果，只是代码中某地方要加绝对值而已，有兴趣可以思考下为什么。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int S = 0;
        for(const int i : nums)
        {
            S += i;
        }
        if(S + target < 0 || (S + target) & 1 == 1)
        {
            return 0;
        }
        int sum = (S + target) >> 1;
        vector<int> dp(sum + 1);
        dp[0] = 1;
        for(const int num : nums)
        {
            for(int i = sum; i >= num; --i)
            {
                dp[i] += dp[i - num];
            }
        }
        return dp[sum];
    }
};