Partition Equal Subset Sum

Medium · 1-D Dynamic Programming

You are given an array of positive integers. Determine whether it is possible to split the array into two groups (using every element exactly once) so that the sum of one group equals the sum of the other. Return true if such a split exists, false otherwise.

Examples

Input:  nums = [1,5,11,5]
Output: true
Why:    The groups [1,5,5] and [11] both sum to 11.

Input:  nums = [1,2,3,5]
Output: false
Why:    The total sum is 11, which is odd, so it cannot be split into two equal halves.

Input:  nums = [1,1]
Output: true
Why:    Each element forms its own group, both summing to 1.

Constraints

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

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Partition Equal Subset Sum

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Partition Equal Subset Sum. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.