目标和

#include <iostream>
#include <vector>

using namespace std;

// 将数组分为两个集合： 正数集合left 与 负数集合right.
// 则由题目描述可得: left + right = sum，left - right = target.
// 即 right = （sum - target) / 2 .

// 1. dp含义: 装满容量为 j 的背包有 dp[j] 种方法.
// 一维数组表示: 
// 二维数组表示：dp[i][j] 表示在数组 nums[i] 的前 i 个数中选取元素,使得这些元素之和等于 j 的方案数.
// 2. 递推公式: dp[j] = max(不放入 nums[i] 的最大组合方案， 放入nums[i] 的最大组合方案).
// 一维数组表示:
// 二维数组表示: 
// 如果 j<nums[i], 则不选 nums[i],dp[i][j] = dp[i-1][j]. 
// 如果 j≥nums[i], 如果不选 nums[i], dp[i][j] = dp[i-1][j]. 如果选 nums[i], dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]].
// 3.边界条件:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int sum = 0;
        for (int& num : nums)
        {
            sum += num;
        }
        int diff = sum - target;
        // 因 nums[i] 为非负整数.
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.size();
        int neg = diff / 2;
        /* 定义dp数组 */
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        // 没有元素选取，元素和只能为 0.
        dp[0][0] = 1;
        /* 遍历 */
        for (int i = 1; i <= n; i++)
        {// 先遍历物品
            for (int j = 0; j <= neg; j++)
            { // 再遍历背包容量
                dp[i][j] = dp[i - 1][j];
                /* 如果背包剩余j的容量大于放的物品nums[i-1],则就可以将物品nums[i-1]放入背包中 */
                if (j >= nums[i - 1])
                {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][neg];
    }
};

int main() {
    vector<int> nums = {0,1,2,3,4,5,6};
    Solution solution;
    int result = solution.findTargetSumWays(nums,1);
    std::cout << result << std::endl;
}