You are given a list of positive integers nums. Return true if you can put every number into
one of two groups so that the two groups have the same total, and false otherwise.
Example 1
- Input
- nums = [2, 7, 4, 3, 6]
- Output
- true
[7, 4] and [2, 3, 6] both add up to 11.Example 2
- Input
- nums = [1, 2, 5]
- Output
- false
Example 3
- Input
- nums = [3, 3, 3]
- Output
- false
Constraints
numsholds 1 to 200 numbers.- 1 ≤
nums[i]≤ 100
Show the pattern
Dynamic programming (1D)
Splitting evenly means finding a group that adds up to half the total, and the sums you can reach with the first k numbers build from those you could reach with the first k − 1: a table indexed by sum.
See dynamic programming (1d) in a visualiserShow the approach
If the total is odd, no split works. Otherwise you need a group adding up to half, half the
total: the other numbers then add up to half too. This is the 0/1 knapsack question "which
sums can a subset make?".
Keep a list reachable where reachable[s] is true when some of the numbers seen so far add up
to s; at first only reachable[0] is true. For each number x, every sum s with
reachable[s − x] becomes reachable. Update s from half down to x, so the sums made with
x in this round aren't extended by x again. The answer is reachable[half].
Time: O(n × S) where S is half the total · Space: O(S)