https://leetcode-cn.com/problems/partition-equal-subset-sum/
0-1背包问题变形
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (auto n : nums) sum += n; if (sum&0x1) return false; //奇数不可能 int n = nums.size(); int target = sum>>1; bool dp[n][target+1]={}; dp[0][0] = true; if (nums[0]<=target) dp[0][nums[0]] = true; for (int i = 1; i < n; ++i) { for (int j = 0; j <= target; ++j) { if (dp[i-1][j]) { dp[i][j] = true; int t = j+nums[i]; if (t<=target) dp[i][t] = true; } } } return dp[n-1][target]; } };参考:
https://time.geekbang.org/column/article/74788
