[LeetCode] 416 Partition Equal Subset Sum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool canPartition(vector<int> &nums) { int sum = std::accumulate(nums.begin(), nums.end(), 0); if ((sum & 1) == 1) return false; sum >>= 1; std::vector<bool> dp(sum + 1, false); dp[0] = true; for (int num : nums) for (int i = sum; i >= num; i--) dp[i] = dp[i] || dp[i - num]; return dp[sum]; } };