Description
Given a list of positive integers nums, return whether you can partition nums into two groups where the sum of the elements in both groups is equal.
Constraints:
n ≤ 2501 ≤ nums[i] ≤ 100
Example 1
Input
nums = [1, 2, 5, 4]
Output
true
Explanation
We can have these partitions: [1, 5] and [2, 4].
Intuition
- make sure the sum of array is even
- Backtracking
Implementation
import java.util.*;
class Solution {
public boolean solve(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
} else {
return canSplit(0, sum / 2 - nums[0], nums);
}
}
private boolean canSplit(int index, int target, int[] nums) {
if (target == 0) {
return true;
} else if (target < 0) {
return false;
}
for (int i = index + 1; i < nums.length; i++) {
if (canSplit(i, target - nums[i], nums)) {
return true;
}
}
return false;
}
}
Time Complexity
- Time: O(nlogn)
- Space:O(logn)
Top comments (0)