0607MediumArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmask

Dealing Counterweights Onto Hoists

Tracked in this browser only

Trains the technique from

LeetCode 698Partition to K Equal Sum Subsets

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A rigging crew has a pile of counterweights and k identical hoists to load. nums[i] is the mass of the i-th counterweight.

Every counterweight has to end up on exactly one hoist, and each of the k hoists has to finish carrying the same total mass. A hoist may take any number of counterweights.

Return true when the pile can be dealt out that way, and false when it cannot.

Examples

Example 1

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true

The masses total 20, so each of the four hoists must carry 5. The groupings 5, then 4 with 1, then 3 with 2, then 3 with 2 use every counterweight once and each comes to 5.

Example 2

Input: nums = [5, 5, 5, 5, 4, 4, 4, 4], k = 3
Output: false

The masses total 36, so each hoist would need 12. The only groups reaching 12 are three 4s, and there is only one such group available, so three hoists cannot all be loaded to 12.

Example 3

Input: nums = [1, 1, 1, 1], k = 3
Output: false

The masses total 4, which is not a multiple of 3, so no equal split across three hoists exists.

Constraints

1 <= k <= nums.length <= 16
1 <= nums[i] <= 10^4
Each distinct mass appears between 1 and 4 times in nums.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_partition_k_subsets(nums: list[int], k: int) -> bool:

Java

public boolean canPartitionKSubsets(int[] nums, int k)

The intended approach

Time O(2^n * n): each of the 2^n sets tries each of the n counterweights.Space O(2^n) for the reachability flags and the per-set masses.

The total mass has to split evenly, so it must be a multiple of `k` and no single counterweight may exceed the per-hoist target. Then fill the hoists one after another rather than all at once: a set of counterweights that has already been dealt out is enough to describe the situation, because the hoists finished before the current one are all exactly at the target, so the mass of the set taken modulo the target is how full the current hoist is. Mark the empty set as reachable and sweep every set in increasing numeric order, extending each reachable set by one undealt counterweight whenever it still fits the current hoist. The pile works out exactly when the complete set is reachable.

Pythonentry point: can_partition_k_subsets

def can_partition_k_subsets(nums, k):
    # O(2^n * n) time, O(2^n) space, and no recursion at all.
    # Which weights are already dealt out is all that matters: from the mass of a
    # chosen set, the remainder after dividing by the per-hoist target says how
    # much of the hoist currently being filled is taken, because every hoist
    # before it was filled exactly to the target.
    total = 0
    for mass in nums:
        total += mass
    if total % k:
        return False
    target = total // k
    for mass in nums:
        if mass > target:
            return False
    n = len(nums)
    full = 1 << n
    loaded = [0] * full
    for mask in range(1, full):
        low = mask & -mask
        idx = low.bit_length() - 1
        loaded[mask] = loaded[mask ^ low] + nums[idx]
    ok = [False] * full
    ok[0] = True
    for mask in range(full):
        if not ok[mask]:
            continue
        partial = loaded[mask] % target
        for i in range(n):
            bit = 1 << i
            if mask & bit:
                continue
            if partial + nums[i] <= target:
                ok[mask | bit] = True
    return ok[full - 1]

The obvious version

Search directly. Sort the counterweights heaviest first, keep the running load of each hoist, and try placing the next counterweight on each hoist that still has room, backtracking on failure. Two hoists carrying the same load are interchangeable, so only the first of them is tried.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_partition_k_subsets(nums, k):
    total = 0
    for mass in nums:
        total += mass
    if total % k:
        return False
    target = total // k
    items = sorted(nums, reverse=True)
    if items[0] > target:
        return False
    n = len(items)
    hoists = [0] * k

    def place(idx):
        if idx == n:
            return True
        tried = set()
        for h in range(k):
            if hoists[h] in tried:
                continue
            tried.add(hoists[h])
            if hoists[h] + items[idx] <= target:
                hoists[h] += items[idx]
                if place(idx + 1):
                    return True
                hoists[h] -= items[idx]
        return False

    return place(0)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in