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.
function canPartition(nums) {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
const target = sum / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (let num of nums) {
for (let 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?
