Partition Equal Subset Sum
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
Given a list of positive integers nums, decide whether it can be split into two groups with equal sums. Every number goes into exactly one of the two groups. Return True if such a split exists, otherwise False.
Each entry is used once: in [2, 6] the 2 cannot be counted twice to make 4.
Examples
Input: nums = [1,5,11,5] Output: True
The total is 22. [1, 5, 5] and [11] both add up to 11.
Input: nums = [1,2,3,5] Output: False
The total is 11, which is odd, so no two equal halves exist.
Constraints
- 1 <= len(nums) <= 200
- 1 <= nums[i] <= 100
Approaches
- Try every subset — time O(2^n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
