plaintext function canPartition(nums) total := sum of all nums if total is odd then return false target := total / 2 dp := array of size (target + 1), all false dp[0] := true Each num in nums for w from target down to num dp[w] := dp[w] OR dp[w - num] return dp[target]
Time: where . Space: .
The backwards loop prevents using the same element twice. If you looped forward, dp[w - num] might already include num from this iteration.
This is the standard 0/1 knapsack space reduction. You'll see it in most subset sum variants.