Equal Weight Crates
MediumBacktracking
Problem
A warehouse must pack all items, with weights weights, into exactly k crates so that every crate carries the same total weight. Items cannot be split.
Return true if this is possible, otherwise false.
Example 1
- Input:
- weights = [4, 3, 2, 3, 5, 2, 1], k = 4
- Output:
- true
Crates [5], [1, 4], [2, 3], [2, 3] all weigh 5.
Example 2
- Input:
- weights = [1, 2, 3, 4], k = 3
- Output:
- false
The total 10 is not divisible by 3.
Constraints
- 1 ≤ k ≤ weights.length ≤ 16
- 1 ≤ weights[i] ≤ 10^4
Hint
Show the first hint
What must each crate weigh? When can you answer 'false' without searching?
Walkthrough
How to approach it
01Clarify before coding
- Must every item be used? Yes.
- Are crates distinguishable? It does not matter: only feasibility is asked, which is why symmetric choices can be pruned.
- Can weights be zero? No, all are at least 1.
02Brute force
Try every assignment of each item to one of the k crates and check the totals.
Cost: O(k^n · n): 4^16 ≈ 4.3 · 10^9 assignments for n = 16, k = 4.
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.