问题描述 链接到标题

416.分割等和子集

解题思路 链接到标题

本题实际上是一个01背包问题，在这个问题中，背包的体积$V$是数组中所有数的的和的一半(向下取整)，物品的价值就是数组中数的取值：

代码 链接到标题 

#include <algorithm>
#include <vector>
using std::vector;
class Solution {
    private:
    int max(int a, int b) {
        return a >= b ? a : b;
    }
  public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        int sum_half = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1)
            return false;
        sum_half = sum / 2;
        vector<int> dp(sum_half + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = sum_half; j >= nums[i]; j--)
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
        return dp[sum_half] == sum_half;
    }
};