Partition Equal Subset Sum
Given an array of non-negative integers, determine if it is possible to partition the array into two subsets such that the sum of elements in both subsets is equal.
Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
Examples:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned into [1, 5, 5] and [11].
Solutions
Dynamic Programming
Time: O(n * sum)Space: O(n * sum)
This solution uses dynamic programming to solve the problem. It calculates the total sum of the array and checks if it is possible to partition the array into two subsets with equal sum. It uses a boolean array dp where dp[i] is true if it is possible to get a sum of i using the numbers in the array.
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
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 i = target;
i >= num;
i--) {
if (dp[i - num]) dp[i] = true;
}
}
return dp[target];
}Follow-up:
Can you solve this problem using a recursive approach?
