Given an array of positive integers, return true if it can be split into two subsets with equal sums.
dp[s] says whether some subset sums to s. For each number, sweep s from high to low so each number is used at most once: dp[s] |= dp[s − x].
1function canPartition(nums: number[]): boolean {2const total = nums.reduce((a, b) => a + b, 0);3if (total % 2) return false;4const half = total / 2;5const dp = new Array(half + 1).fill(false);6dp[0] = true;7for (const x of nums)8for (let s = half; s >= x; s--)9if (dp[s - x]) dp[s] = true;10return dp[half];11}
dp[0] = true: the empty subset sums to 0.
Space: play/pause · ←/→: step