Leetcode 416. 分割等和子集 c++

链接：
https://leetcode-cn.com/problems/partition-equal-subset-sum/

主要思路：
从一堆数据里选出一部分可以达到某一个数值，这个算是动态规划。
1.先计算出目标数据的大小，总和的一半。
2.遍历这个数组，对于每一个dp的元素，如果i位true（即有达到当前数字的方案），则i+n也为true。

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = 0;
        for (auto n : nums) {
            sum += n;
        }
        if (sum & 1) {
            return false;
        }
        bool ret = false;
        int half = sum >> 1;

        bool* dp = new bool[half + 1];
        memset(dp, 0, sizeof(bool) * (half + 1));
        dp[0] = true;
        for (auto n : nums) {
            for (int i = half - n; i >= 0; i--) {
                if (dp[i] == true) {
                    dp[i + n] = true;
                }
            }
            if (dp[half]) {
                ret = true;
                break;
            }
        }
        delete[] dp;

        return ret;
    }
};