Partition Equal Subset Sum Problem
Description
LeetCode Problem 416.
Given a non-empty array nums 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.
Example 1:
1
2
3
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
1
2
3
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
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool checkPar(vector<int>& nums, int target, int len) {
if (target == 0)
return true;
if ((target != 0) && (len == 0))
return false;
if (nums[len-1] > target)
return false;
return checkPar(nums, target-nums[len-1], len-1) ||
checkPar(nums, target, len-1);
}
bool canPartition(vector<int>& nums) {
int len = nums.size();
int target = 0;
for (int i = 0; i < len; i ++) {
target += nums[i];
}
if (target % 2 != 0)
return false;
return checkPar(nums, target / 2, len);
}
};