Fairest Stone Split
Split the stones whose weights are listed in stones into two piles; every stone goes into one of the piles, and either pile may be empty. Return the smallest possible difference between the weights of the two piles, that is the heavier pile's weight minus the lighter pile's weight. An empty list gives 0.
Example 1
stones [3,1,4,2,2]
returns 0
The piles 3 + 1 + 2 and 4 + 2 both weigh 6, so the difference is 0.
Example 2
stones [10,4,3]
returns 3
Putting the 10 alone against 4 + 3 leaves a difference of 3, the smallest possible.
Constraints
0 <= len(stones) <= 201 <= stones[i] <= 50
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Fewest Perfect SquaresMedium
- Gems That ClashMedium
- Hands That Hit the TargetMedium
- Keystrokes to TransformMedium
- Knight on the KeypadMedium
- Letter DecodingsMedium
- Lightest Deletions to MatchMedium
- Longest Climbing ChainMedium