mediumDynamic programming, 1D target 25 min
Split into two equal sums
You get a list of positive integers nums. Decide whether you can split it into two groups with equal sums. Every number goes into exactly one of the two groups, and equal values at different positions are separate numbers.
Return True if such a split exists and False if it does not.
Example 1
Input
nums = [3, 1, 5, 9, 2]OutputTrueThe total is 20. The groups [9, 1] and [3, 5, 2] each sum to 10.
Example 2
Input
nums = [2, 4, 7]OutputFalseThe total is 13, an odd number, so two equal halves are impossible.
Example 3
Input
nums = [3, 3, 4, 6]OutputFalseThe total is 16, so one group must sum to 8. A single number is at most 6, any two make 6, 7, 9 or 10, and any three make at least 10.
Constraints
1 ≤ len(nums) ≤ 200
1 ≤ nums[i] ≤ 100
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.