leetcode 链接：494. 目标和

题目

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

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例：

  1. 输入：nums = [1,1,1,1,1], target = 3
  2. 输出：5
  3. 解释：一共有 5 种方法让最终目标和为 3 。
  4. -1 + 1 + 1 + 1 + 1 = 3
  5. +1 - 1 + 1 + 1 + 1 = 3
  6. +1 + 1 - 1 + 1 + 1 = 3
  7. +1 + 1 + 1 - 1 + 1 = 3
  8. +1 + 1 + 1 + 1 - 1 = 3
输入：nums = [1], target = 1
输出：1

解答 & 代码

可转换为 01背包问题 

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int len = nums.size();
        // 求数组中所有元素的和
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum += nums[i];
        // 特例：直接返回 false
        if((target < 0 && -sum > target) || (target > 0 && sum < target) ||
            (sum + target) % 2 == 1)
            return 0;

        // 设X代表数组中最终代表正数的元素的和
        // 设Y代表数组中最终代表负数的元素的和
        // 则 X+Y=sum，X-Y=target，因此有 X=(sum+target)/2
        // 这个 X 就是 01 背包问题的目标值
        int posTarget = (target + sum) / 2;
        vector<int> dp(posTarget + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < len; ++i)                // 外层循环遍历nums数组
        {
            int val = nums[i];
            for(int j = posTarget; j >= val; --j)    // 内层循环倒序遍历 target
                dp[j] += dp[j - val];
        }
        return dp[posTarget];
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 98.54% 的用户
内存消耗：9 MB, 在所有 C++ 提交中击败了 56.10% 的用户