鏈接：
https://leetcode-cn.com/problems/partition-equal-subset-sum/
主要思路：
從一堆數(shù)據(jù)里選出一部分可以達(dá)到某一個(gè)數(shù)值缘眶，這個(gè)算是動(dòng)態(tài)規(guī)劃贿讹。
1.先計(jì)算出目標(biāo)數(shù)據(jù)的大小，總和的一半凯旋。
2.遍歷這個(gè)數(shù)組粱玲，對(duì)于每一個(gè)dp的元素上忍，如果i位true（即有達(dá)到當(dāng)前數(shù)字的方案）怒见，則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;
}
};
