Given an integer array , return true if you can partition it into two subsets with equal sums. For example, can be split into and , 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 , you need to find a subset that sums to exactly . That's subset sum. Before reading on, think about this: when is it impossible to partition? What condition on the total sum guarantees failure?