// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem416.h"
#include <numeric>
using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=416 lang=cpp
 *
 * [416] 分割等和子集
 */

// @lc code=start
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) {
            return false;
        }
        int pack = sum / 2;
        int n = nums.size();
        vector<bool> dp(pack + 1, false);

        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = pack; j >= 0; --j) {
                if (nums[i] <= j) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp.back();
    }
};
// @lc code=end