Can we pick a subset summing to half of total?
If total sum is odd, impossible.
Otherwise target = sum/2. Do 0/1 knapsack boolean DP:
dp[t] = reachable sum t.
Iterate nums and update t downward to avoid reuse.
A partition into equal sums exists iff some subset sums to target.
Can we pick a subset summing to half of total?
If total sum is odd, impossible.
Otherwise target = sum/2. Do 0/1 knapsack boolean DP:
dp[t] = reachable sum t.
Iterate nums and update t downward to avoid reuse.
A partition into equal sums exists iff some subset sums to target.