416. Partition Equal Subset Sum
1. 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.
2. Example
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.
3. Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
4. Solutions
Greedy && Heap
n = nums.size(), s = sum(nums)
Time complexity: O(ns)
Space complexity: O(s)
class Solution {
public:
bool canPartition(vector<int> &nums) {
const int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
vector<bool> formable(target + 1, false);
formable[0] = true;
for (int num : nums) {
for (int j = target; j >= num; --j) {
formable[j] = formable[j] || formable[j - num];
}
if (formable[target]) {
return true;
}
}
return false;
}
};