1. Total sum
Equal partition requires splitting the total in half.
const total = nums.reduce((sum, num) => sum + num, 0)Typorithm · medium
Partition Equal Subset Sum
▷ Interactive algorithm labpartition-equal-subset-sum-dpdynamic-programmingsubsetknapsackboolean-dp
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Partition Equal Subset Sum
Dynamic Programming
Partition Equal Subset Sum turns equal partition into a subset-sum DP for half of the total.
If the total is odd, no equal split exists.
Otherwise, ask whether any subset reaches total / 2.
Reverse sum iteration makes each number single-use.
Preparing algorithm lab…
01
Target: total / 2.
02
State: dp[sum] is reachable.
03
Base: dp[0] = true.
04
Reverse loop prevents reuse.
function canPartition(nums) {
const total = nums.reduce((sum, num) => sum + num, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let sum = target; sum >= num; sum--) {
dp[sum] = dp[sum] || dp[sum - num];
}
}
return dp[target];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Odd total
Odd total cannot split into two equal integer sums.
if (total % 2 !== 0) return false3. Zero sum
Sum 0 is always reachable by choosing no numbers.
dp[0] = true4. Reach target
A sum is reachable if it already was or if num completes it.
dp[sum] = dp[sum] || dp[sum - num]A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.