Show problems as
Classic problem #698MediumArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmask

Partition to K Equal Sum Subsets

Real-world version: Dealing Counterweights Onto Hoists
Tracked in this browser only
Read Partition to K Equal Sum Subsets on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_partition_k_subsets(nums: list[int], k: int) -> bool:
Java
public boolean canPartitionKSubsets(int[] nums, int k)

More on the same topics