Description
Given an integer array nums
, return true
if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false
otherwise.
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
Solution
Python3
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
total = sum(nums)
target = total // 2
if total & 1: return False
bits = 1
for x in nums:
bits |= (bits << x)
return (bits & (1 << target)) > 0
C++
class Solution {
public:
bool canPartition(vector<int>& nums) {
bitset<10001> bits(1);
int total = 0;
for (auto n:nums)
bits |= bits << n, total += n;
return !(total&1) && bits[total / 2];
}
};