Two Equal Cargo Holds
Medium1-D Dynamic Programming
Problem
A ship has two cargo holds and a list of crates with positive weights weights. Every crate must go into exactly one hold.
Return true if the crates can be divided so that both holds carry exactly the same total weight.
Example 1
- Input:
- weights = [3, 1, 5, 9, 2]
- Output:
- true
Total 20: {9, 1} and {3, 5, 2} both weigh 10.
Example 2
- Input:
- weights = [2, 2, 3]
- Output:
- false
The total 7 is odd, so no equal split exists.
Constraints
- 1 ≤ weights.length ≤ 200
- 1 ≤ weights[i] ≤ 100
Hint
Show the first hint
If the total is odd, stop. Otherwise, what weight must ONE hold carry?
Walkthrough
How to approach it
01Clarify before coding
- Must every crate be placed? Yes, each in exactly one hold.
- Are weights positive? Yes, so sums only grow as crates are added.
- Do I need the actual split? No, only whether it exists.
02Brute force
Try all 2^n assignments of crates to holds and compare the two sums.
Cost: O(2^n · n): 2^200 assignments is far beyond any budget.
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.