Partition Equal Subset Sum
Real-world version: Even Split of Crate LoadsThe statement here is our own: the same inputs, outputs and technique.
A dispatcher has two identical trailers standing at a loading bay and an integer array weights, where weights[i] is the weight of the i-th crate.
Every crate has to be rolled onto exactly one of the two trailers, and no crate may be left on the bay or cut apart. The bay foreman wants the two trailers to leave carrying the same total weight.
Return true if such a hand-out exists and false if it does not. A trailer is allowed to end up with any number of crates, and the crates do not have to be handed out in the order they are listed.
Examples
Example 1
- Input
- weights = [6, 2, 4, 8]
- Output
- true
Rolling the 6 and the 4 onto one trailer leaves the 2 and the 8 for the other, and both leave with 10.
Example 2
- Input
- weights = [7, 3, 9]
- Output
- false
The crates weigh 19 in total, an odd figure, so no hand-out can leave the two trailers level.
Example 3
- Input
- weights = [3, 3, 3, 4, 5]
- Output
- true
The three crates of weight 3 go on one trailer and the 4 and the 5 go on the other, and each trailer leaves with 9.
Constraints
- 1 <= weights.length <= 200
- 1 <= weights[i] <= 100
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def can_split_crates(weights: list[int]) -> bool:public boolean canSplitCrates(int[] weights)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's