Partition Equal Subset Sum
Problem
Given an array of positive integers nums, decide whether it can be partitioned into two subsets whose sums are equal. Equivalently: is there a subset of nums summing to total/2?
nums = [1, 5, 11, 5]truedef can_partition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for s in range(target, x - 1, -1):
dp[s] = dp[s] or dp[s - x]
return dp[target]function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2) return false;
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const x of nums) {
for (let s = target; s >= x; s--) {
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
for (int x : nums) total += x;
if ((total & 1) == 1) return false;
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int x : nums) {
for (int s = target; s >= x; s--) {
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}
}bool canPartition(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total & 1) return false;
int target = total / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int x : nums) {
for (int s = target; s >= x; s--) {
if (dp[s - x]) dp[s] = true;
}
}
return dp[target];
}Explanation
Splitting the array into two equal halves is the same as asking a simpler question: can we pick a subset that sums to exactly total / 2? If we can, the leftover numbers automatically form the other half. This turns it into a classic 0/1 knapsack.
First a quick exit: if the total is odd, no equal split exists, so we return false right away. Otherwise we set target = total / 2.
We keep a boolean array dp where dp[s] means "some subset adds up to s". We start with dp[0] = true (the empty set sums to zero). For each number x, we mark dp[s] true whenever dp[s - x] was already reachable.
The loop over s runs downward (from target to x). That ordering is important: it stops us from reusing the same number twice, since the smaller index it depends on still reflects the array before x was added.
Example: nums = [1, 5, 11, 5], total 22, target 11. The subset {1, 5, 5} reaches 11, so dp[11] becomes true and the answer is true.