All problems

Partition Equal Subset Sum

Medium · dynamic programming

Given a list of positive integers nums, decide whether you can split it into two groups with exactly the same sum. Every number must go into one group or the other, and each number can be used only once.

Return True if such a split exists, and False otherwise. A list whose total is odd can never be split evenly, and a list with one number has no way to fill both groups.

Examples

Example 1

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

Output: True

Put 11 in one group and 1, 5, 5 in the other. Both groups sum to 11.

Example 2

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

Output: False

The total is 11, which is odd, so two equal groups are impossible.

Example 3

Input: nums = [2, 2, 3, 5]

Output: False

The total is 12, so each group needs 6, but no choice of these numbers adds up to 6.

Constraints