题目来源
给一个数组，问能否把数组切分为两组，这两组元素的和是一样的。
想着就应该用dp，然后没想到怎么用，然后又看了下答案…其实也是蛮简单的一道题。
首先求出数组和，若和为奇数，则false，否则求出sum的一半，进行遍历。dp数组存储的是数组中能否有元素和等于该索引，遍历一遍元素，然后每次遍历到某个元素的时候都更新dp数组。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1 == 1)
return false;
int target = sum >> 1, n = nums.size();
vector<int> dp(target+1, 0);
dp[0] = 1;
for (auto num : nums)
for (int i=target; i>=num; i--)
dp[i] = dp[i] || dp[i-num];
return dp[target];
}
};
