Back to DSA
Partition Equal Subset Sum
mediumDetermine whether an integer array can be split into two groups such that both groups have identical sums.
Examples
Example 1:
Input:
nums = [3,3,3,4,5]Output:
trueExplanation: One valid split is {3,3,3} and {4,5}, both summing to 9.
Example 2:
Input:
nums = [1,2,5]Output:
falseExplanation: Total is 8, which is even, but no subset sums to 4.
Hints
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
}Time complexity
O(n * sum)Space complexity
O(sum)