分割等和子集

 1bool canPartition(vector<int>& nums)
 2{
 3    int sum = reduce(nums.begin(), nums.end());
 4    if(sum % 2 != 0) return false;
 5    sum /= 2;
 6
 7    int n = nums.size();
 8    std::vector<bool> dp(sum + 1, false);
 9    dp[0] = true;
10    for(int num : nums)
11    {
12        for(int i = sum; num <= i; i--)
13        {
14            if(dp[i - num]) dp[i] = true;
15        }
16        if(dp[sum]) return true;
17    }
18    return dp[sum];
19}