# 416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers , find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Both the array size and each of the array element will not exceed 100.

Example 1:

``````Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
``````

Example 2:

``````Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
``````

dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

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

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
bitset<5001> bits(1);
int sum = accumulate(nums.begin(), nums.end(), 0);
for (int num : nums) bits |= bits << num;
return (sum % 2 == 0) && bits[sum >> 1];
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/416

Partition to K Equal Sum Subset

https://leetcode.com/problems/partition-equal-subset-sum/

https://leetcode.com/problems/partition-equal-subset-sum/discuss/90592/01-knapsack-detailed-explanation

https://leetcode.com/problems/partition-equal-subset-sum/discuss/90590/Simple-C++-4-line-solution-using-a-bitset

https://leetcode.com/problems/partition-equal-subset-sum/discuss/90588/Concise-C++-Solution-summary-with-DFS-DP-BIT

https://leetcode.com/problems/partition-equal-subset-sum/discuss/90627/Java-Solution-similar-to-backpack-problem-Easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation