leetExpert
Practice

Partition Equal Subset Sum

Module 24 · Dynamic Programming

Problem

Given an integer array nums of positive integers, return true if it can be partitioned into TWO subsets with EQUAL sum. (LeetCode 416.)

Examples

Example 1

Inputnums = [1,5,11,5]Outputtrue

Explanation. [1,5,5] and [11], both sum to 11

Example 2

Inputnums = [1,2,3,5]Outputfalse

Explanation. total is 11, odd — can't split evenly

Constraints

1 ≤ nums.length ≤ 200, values in [1, 100].

Attempt it first

This is 0/1 knapsack in disguise — the Knapsack-Style DP concept lesson's exact shape, with each number treated as an "item" of weight (and value) equal to itself. Before opening anything, work out the reduction: if the total sum is S, what must be true about S before any partition into two equal-sum subsets is even possible, and what SINGLE knapsack question — about ONE target capacity — is equivalent to "can this array be split into two equal halves"?