Partition Equal Subset Sum
MediumDynamic Programming
You are given an array of positive integers nums. Return True if you can split the elements into two groups with equal sums, and False otherwise.
Every element must go into exactly one of the two groups. Elements with equal values are still separate items.
Example 1
- Input:
- nums = [3, 1, 4, 2, 2]
- Output:
- True
- Explanation
- The total is 12, so each group needs 6:
{4, 2}and{3, 1, 2}both sum to 6.
Example 2
- Input:
- nums = [1, 2, 5]
- Output:
- False
- Explanation
- The total 8 is even, so each group would need 4, but no subset of 1, 2 and 5 adds up to 4.
Example 3
- Input:
- nums = [2, 2, 3]
- Output:
- False
- Explanation
- The total 7 is odd, so it can never be split into two equal halves.
Constraints
- 1 ≤
nums.length≤ 200 - 1 ≤
nums[i]≤ 100