Equal Cargo Halves
Problem
A cargo plane has two holds that must carry exactly the same weight. You have parcels with positive weights weights, and every parcel must go into one of the two holds.
Return true if the parcels can be split so both holds weigh the same, otherwise false.
Example 1
- Input:
- weights = [3, 1, 5, 9, 2]
- Output:
- true
The total is 20, and {9, 1} and {3, 5, 2} both weigh 10.
Example 2
- Input:
- weights = [2, 4, 7]
- Output:
- false
The total 13 is odd, so two equal halves are impossible.
Example 3
- Input:
- weights = [4, 4]
- Output:
- true
Constraints
- 1 ≤ weights.length ≤ 200
- 1 ≤ weights[i] ≤ 100
Hint
Show the first hint
If one hold weighs exactly half the total, what does the other weigh?
Walkthrough
How to approach it
01Clarify before coding
- Must every parcel be used? Yes, each goes into exactly one hold.
- Are weights positive integers? Yes, which keeps the reachable sums bounded by the total.
- Does the number of parcels per hold matter? No, only the weight.
02Brute force
Try every assignment of parcels to the two holds and check the weights.
Cost: O(2^n · n): for n = 200 this never finishes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.