Partition Equal Subset Sum

The key idea

Two equal halves means each half sums to total / 2. So the question reduces to: can any subset of nums reach exactly target = total / 2? If total is odd, the answer is immediately false. Otherwise it is a classic 0/1 subset-sum decision over the target.

Problem

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal, or false otherwise. Each element of nums must belong to exactly one of the two subsets, and the two subsets together use every element.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100

Examples

Input: nums = [1,5,11,5] Output: true

Input: nums = [1,2,3,5] Output: false

Complexity

Time: O(n * target) Space: O(target)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →