494. 目标和#

1
给你一个 只包含正整数 的 非空 数组 nums 。
2

3
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
4

5

6

7
示例 1：
8

9
输入：nums = [1,5,11,5]
10
输出：true
11
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
12
示例 2：
13

14
输入：nums = [1,2,3,5]
15
输出：false
16
解释：数组不能分割成两个元素和相等的子集。
17

18

19
提示：
20

21
1 <= nums.length <= 200
22
1 <= nums[i] <= 100

1
class Solution {
2
public:
3
    int findTargetSumWays(vector<int>& nums, int target) {
4
        int sum = accumulate(nums.begin(), nums.end(), 0);
5
        if((sum - target) % 2 == 1 || sum < target) return false;
6

7
        int n = (sum - target) / 2;
8
        vector<int> dp(n + 1, 0);
9
        dp[0] = 1;
10
        for(int i : nums)
11
        {
12
            for (int j = n; j >= i; j--) {
13
                dp[j] += dp[j - i];
14
            }
15
        }
16
        return dp[n];
17
    }
18
};