Partition problem
Problem Statement
Given an array of positive integers, determine whether it can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example:
- Input:
arr = [1, 5, 11, 5] - Output:
true(The array can be partitioned as 5 and 11, both summing to 11)
Noob-Friendly Explanation
Imagine you and your friend want to split a pile of candy bars. Each candy bar has a different weight. You want to divide all the candy bars into two groups so that both groups weigh exactly the same. Is this possible? That's exactly what this problem asks! If the total weight is odd, it's impossible (you can't split an odd number evenly). If it's even, we need to find if some candy bars add up to exactly half the total.
Approach 1: Brute Force
Intuition
Try all possible subsets. For each element, either put it in subset 1 or subset 2. Check if any division results in equal sums. This is equivalent to: can we find a subset that sums to totalSum / 2?
Algorithm
- Compute the total sum. If it's odd, return false.
- Target = sum / 2.
- Use recursion: for each element, include or exclude it.
- If we reach the target, return true.
class Solution {
public static boolean canPartitionBrute(int[] arr) {
int sum = 0;
for (int num : arr) sum += num;
// If sum is odd, can't partition equally
if (sum % 2 != 0) return false;
return canFindSubset(arr, arr.length - 1, sum / 2);
}
private static boolean canFindSubset(int[] arr, int index, int target) {
if (target == 0) return true;
if (index < 0 || target < 0) return false;
// Include current element or exclude it
return canFindSubset(arr, index - 1, target - arr[index])
|| canFindSubset(arr, index - 1, target);
}
public static void main(String[] args) {
int[] arr = {1, 5, 11, 5};
System.out.println(canPartitionBrute(arr)); // Output: true
int[] arr2 = {1, 2, 3, 5};
System.out.println(canPartitionBrute(arr2)); // Output: false
}
}Complexity Analysis
- Time Complexity: O(2^n) - each element has two choices
- Space Complexity: O(n) - recursion stack depth
Approach 2: Optimal
Intuition
This is the classic Subset Sum problem in disguise. Use a 2D boolean DP table where dp[i][j] indicates whether a subset of the first i elements can sum to j. We only need to check if dp[n][sum/2] is true.
Algorithm
- Compute total sum. If odd, return false. Set
target = sum / 2. - Create a boolean
dptable of size(n+1) x (target+1). dp[i][0] = truefor alli(empty subset sums to 0).- For each element, either include or exclude:
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]]. - Return
dp[n][target].
class Solution {
public static boolean canPartition(int[] arr) {
int sum = 0;
for (int num : arr) sum += num;
if (sum % 2 != 0) return false;
int target = sum / 2;
int n = arr.length;
boolean[][] dp = new boolean[n + 1][target + 1];
// Base case: sum 0 is always achievable (empty subset)
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// Fill the table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
// Exclude current element
dp[i][j] = dp[i - 1][j];
// Include current element (if it doesn't exceed current target)
if (arr[i - 1] <= j) {
dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
}
}
}
return dp[n][target];
}
public static void main(String[] args) {
int[] arr = {1, 5, 11, 5};
System.out.println(canPartition(arr)); // Output: true
int[] arr2 = {1, 2, 3, 5};
System.out.println(canPartition(arr2)); // Output: false
}
}Complexity Analysis
- Time Complexity: O(n * sum) - filling the 2D table where sum = total/2
- Space Complexity: O(n * sum) - the 2D dp table