Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 416 Partition Equal Subset Sum - Problem Statement

LeetCode 416

Given an integer array numsnums, return true if you can partition it into two subsets with equal sums. For example, [1,5,11,5][1, 5, 11, 5] can be split into [1,5,5][1, 5, 5] and [11][11], both summing to 11. At first glance, this looks nothing like knapsack. There's no weight limit, no values.

But here's the connection: if the total sum is SS, you need to find a subset that sums to exactly S/2S/2. That's subset sum. Before reading on, think about this: when is it impossible to partition? What condition on the total sum guarantees failure?