AlgoMaster Logo

Partition to K Equal Sum Subsets

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're given an array and need to split every element into exactly k groups where each group has the same sum. Every element must belong to exactly one group, and no group can be empty.

If the total sum of the array isn't divisible by k, the answer is immediately false. If it is divisible, each subset must sum to totalSum / k. So the problem reduces to: can we partition all elements into k subsets, each summing to a fixed target?

This is a partitioning problem, which belongs to the NP-complete family, so there is no known polynomial-time algorithm for it. The constraint nums.length <= 16 is what makes it tractable here. With at most 16 elements, exponential approaches like backtracking or bitmask DP run fast enough. The work is in choosing one of those approaches and pruning it well enough to pass within time limits.

Key Constraints:

  • 1 <= nums.length <= 16 - With n up to 16, there are 2^16 = 65,536 possible subsets. That bound is small enough for bitmask DP and for backtracking with pruning.
  • 1 <= k <= nums.length - When k equals n, every element must be its own subset, which forces all elements to be equal.
  • 1 <= nums[i] <= 10^4 - The total sum stays at most 16 * 10^4 = 160,000, which fits comfortably in a 32-bit integer, so there is no overflow concern.

Approach 1: Backtracking (Bucket Filling)

Intuition

Model the problem as k buckets, each needing to hold a sum of target = totalSum / k. We place numbers into buckets one at a time. If a number fits in a bucket (adding it does not exceed target), we place it and move to the next number. If no bucket can hold the current number, we backtrack and undo the previous placement.

A plain version of this explores k^n placements, too many even for n = 16. Pruning is what makes it practical. Four pruning rules cut the search space sharply:

  1. Sort the array in descending order. Larger numbers are harder to place, so trying them first reaches a dead end sooner and prunes more of the tree.
  2. If any single number exceeds the target, return false immediately.
  3. Stop after the first empty bucket. When the current number does not fit any bucket so far and the next bucket is empty (sum 0), every remaining empty bucket is interchangeable. Placing the number in one empty bucket produces the same state as placing it in any other, so trying the rest only repeats failed work. The code expresses this with if (buckets[i] == 0) break;.
  4. The same break also handles the case where the number was placed in an empty bucket but the recursion failed. Backing out and trying a different empty bucket would explore an identical subtree, so the loop stops there too.

Algorithm

  1. Compute the total sum. If it's not divisible by k, return false.
  2. Set target = totalSum / k. If any element exceeds target, return false.
  3. Sort the array in descending order.
  4. Create an array of k buckets, each starting at 0.
  5. For each number (starting from the largest), try placing it in each bucket:
    • If the bucket's current sum plus the number doesn't exceed target, place it and recurse.
    • If the bucket's sum equals 0 (empty bucket) and we failed, don't try other empty buckets.
    • Backtrack if no valid placement exists.
  6. If all numbers are placed successfully, return true.

Example Walkthrough

nums (sorted desc)
1Initial: sorted descending, target=5, 4 buckets all empty
0
5
index
1
4
2
3
3
3
4
2
5
2
6
1
buckets
14 empty buckets, each needs to reach target sum = 5
0
0
1
0
2
0
3
0
1/7

Code

Backtracking is fast in practice, but its worst case is O(k^n) and the actual runtime depends on how well the pruning rules fit a given input. The next approach uses bitmask dynamic programming, which trades extra memory for a fixed O(n * 2^n) bound that does not depend on pruning.

Approach 2: Bitmask DP

Intuition

Instead of filling buckets one number at a time, we represent which numbers have been used so far as a bitmask. With n <= 16 numbers, a 16-bit integer encodes any subset of numbers.

The state is the bitmask of used numbers, and for each state we store whether it can be reached such that every completed subset along the way summed to exactly target. The running sum of used elements, taken modulo target, tells us how full the current bucket is. When that sum crosses a multiple of target, one bucket is complete and the next one starts, so there is no need to track a bucket index separately.

Algorithm

  1. Compute total sum. If not divisible by k, return false.
  2. Set target = totalSum / k. If any element exceeds target, return false.
  3. Create a boolean DP array of size 2^n, initialized to false. Set dp[0] = true (empty set is valid).
  4. For each bitmask state from 0 to 2^n - 1:
    • If dp[state] is false, skip it.
    • Compute the current sum of all used elements, then take currentSum % target to find how much of the current bucket is filled.
    • For each unused number j, if adding nums[j] doesn't exceed the current bucket's remaining capacity, set dp[state | (1 << j)] = true.
  5. Return dp[(1 << n) - 1] (whether using all numbers is achievable).

Example Walkthrough

nums
1Initial: target=5, mask=000 (no elements used), bucket fill=0
0
2
1
3
2
5
dp states
1Base case: empty set (mask=000) is reachable, sum=0
000
:
T, sum=0
1/6

Code