A cargo plane has two holds that must carry exactly the same weight. Given the crate weights weights, return True if the crates can be divided into two groups (each crate in exactly one group, a group may be empty) with equal total weight, and False otherwise.
Examples
Input: weights = [3, 1, 4, 2, 2]
Output: True
Explanation: {4, 2} and {3, 1, 2} both weigh 6.
Input: weights = [1, 5, 3]
Output: False
Constraints
0 <= len(weights) <= 1001 <= weights[i] <= 200- Target complexity: O(n * sum) time; trying all 2^n subsets is far too slow.
Goals
- Reduce an equal-split question to reaching half the total
- Update a reachable-sums table backwards so each item is used at most once