Title: Partition Array into K Equal Sum Subsets
In this guide, you’ll learn how to solve the Partition Array into K Equal Sum Subsets problem in Java. Given an integer array nums and an integer k, the task is to decide whether the array can be split into k non-empty subsets so that every subset has the same sum.
This is a classic backtracking problem that interviewers like because it mixes array partitioning, pruning, and recursion. Let’s explore the full algorithm, trace it by hand on a small example, and cover the edge cases and follow-up questions an interviewer is likely to ask.
Understanding the Problem
You are given an array nums of positive integers and an integer k. The task is to determine whether nums can be divided into k subsets, each with the same sum, using every element exactly once.
Every element must belong to exactly one subset, no subset may be empty, and the order of elements inside a subset does not matter. If the total sum of the array is not evenly divisible by k, an equal partition is impossible before you even look at the individual values.
1 <= k <= nums.length- All values in
numsare positive integers in the examples used in this article. - The target subset sum is
totalSum / k, sototalSum % kmust equal0.
Approach to Solve
The idea is to try to fill k empty buckets, one element at a time, so that every bucket ends up holding exactly target = totalSum / k. Backtracking explores every placement and undoes a choice as soon as it cannot lead to a solution.
- Compute the total sum of
nums. IftotalSum % k != 0, returnfalseimmediately since an equal split is impossible. - Compute
target = totalSum / kand sortnumsin ascending order. - If the largest element exceeds
target, returnfalse, since no bucket could ever hold it. - Create a
bucketsarray of sizek, all initialized to0. - Starting from the largest unplaced element, try adding it to each bucket in turn. Only attempt a bucket when
buckets[i] + current <= target. - Recurse on the next, smaller element after a successful placement. If the recursive call fails, undo the addition and try the next bucket.
- If an element was tried against an empty bucket and failed, skip the remaining empty buckets for that element, since they are symmetric and retrying them wastes time.
- When every element has been placed, all
kbuckets hold exactlytarget, so returntrue.
Java Program
import java.util.Arrays;
public class PartitionArrayIntoKEqualSumSubsets {
public static boolean canPartitionKSubsets(int[] nums, int k) {
if (k <= 0 || k > nums.length) {
return false;
}
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
if (totalSum % k != 0) {
return false;
}
int target = totalSum / k;
Arrays.sort(nums);
int n = nums.length;
if (nums[n - 1] > target) {
return false;
}
int[] buckets = new int[k];
return fillBuckets(nums, n - 1, buckets, target);
}
private static boolean fillBuckets(int[] nums, int index, int[] buckets, int target) {
if (index < 0) {
return true;
}
int current = nums[index];
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] + current <= target) {
buckets[i] += current;
if (fillBuckets(nums, index - 1, buckets, target)) {
return true;
}
buckets[i] -= current;
}
if (buckets[i] == 0) {
break;
}
}
return false;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 3, 5, 2, 1};
int k = 4;
boolean result = canPartitionKSubsets(nums, k);
System.out.println("Can partition into " + k + " equal sum subsets: " + result);
}
}Explanation of the Program
The canPartitionKSubsets method first rules out the impossible cases: a k that is too large for the array, and a sum that does not divide evenly by k. These checks avoid wasted recursion.
After sorting nums ascending, the method also rejects the input early if the single largest element is already bigger than target, since that element could never fit into any bucket.
fillBuckets is the recursive backtracking helper. It walks nums from the last index, the largest value, down to 0. For each value, it tries every bucket in order.
When a bucket can accept the current value without exceeding target, the method adds the value, recurses on the next index, and if that recursive call returns false, subtracts the value back out before trying the next bucket. This add, recurse, undo pattern is the heart of backtracking.
The if (buckets[i] == 0) break; line is a pruning optimization. Placing the same element into any one of several currently empty buckets produces an identical state, so only the first empty bucket needs to be tried.
Step-by-Step Trace
Trace the algorithm on nums = [1, 1, 2, 2, 4] with k = 2. The total sum is 10, so target = 5. After sorting, the array is processed from the largest value, 4, down to the smallest.
| Step | Element | Buckets (before) | Bucket Chosen | Buckets (after) | Why |
|---|---|---|---|---|---|
| 1 | 4 | [0, 0] | Bucket 0 | [4, 0] | Bucket 0 is empty, so 4 fits immediately. |
| 2 | 2 | [4, 0] | Bucket 1 | [4, 2] | Bucket 0 would become 6, over the target of 5, so bucket 1 is used. |
| 3 | 2 | [4, 2] | Bucket 1 | [4, 4] | Bucket 0 would overflow again; bucket 1 still has room. |
| 4 | 1 | [4, 4] | Bucket 0 | [5, 4] | Bucket 0 reaches exactly the target. |
| 5 | 1 | [5, 4] | Bucket 1 | [5, 5] | Bucket 0 is already full; bucket 1 reaches the target too. |
At the end of every step, no bucket ever exceeds target, and once all five elements are placed, both buckets equal target exactly, so the method returns true.
Examples
Example 1: A Valid Partition
nums = {4, 3, 2, 3, 5, 2, 1} and k = 4. The total sum is 20, so each subset must sum to 5. One valid split is {5}, {1, 4}, {2, 3}, {2, 3}.
int[] nums = {4, 3, 2, 3, 5, 2, 1};
int k = 4;
System.out.println(canPartitionKSubsets(nums, k));
// Output: trueExample 2: Sum Not Divisible by K
nums = {1, 2, 3, 4} and k = 3. The total sum is 10, and 10 % 3 != 0, so the method returns false before any backtracking starts.
int[] nums = {1, 2, 3, 4};
int k = 3;
System.out.println(canPartitionKSubsets(nums, k));
// Output: falseExample 3: A Single Element Too Large
nums = {6, 1, 1, 1, 1} and k = 2. The total sum is 10, so target = 5, but the largest element, 6, already exceeds the target, so no bucket could ever hold it.
int[] nums = {6, 1, 1, 1, 1};
int k = 2;
System.out.println(canPartitionKSubsets(nums, k));
// Output: falseCommon Mistakes to Avoid
These are the mistakes candidates most often make when implementing this algorithm under interview pressure.
- Skipping the sum divisibility check – jumping straight into backtracking without checking
totalSum % kwastes time on an input that can never be split evenly. Always compute and checktotalSum % k != 0before doing anything else. - Not validating k against array length – allowing
kto exceednums.lengthlets the algorithm try to create more non-empty subsets than there are elements, which can never succeed but still burns recursion. Returnfalseimmediately whenk > nums.length. - Placing small elements first – iterating
numsfrom index0instead of starting with the largest value lets many bad placements survive deep into the recursion before failing, which is dramatically slower. Sort the array and always place the largest remaining element first so failures are detected early. - Forgetting the empty-bucket shortcut – without the
buckets[i] == 0break, the algorithm retries the same element against several interchangeable empty buckets, multiplying the search space for no benefit. Break out of the loop the first time an empty bucket is tried for the current element. - Allocating a new buckets array per call – copying
bucketsbefore each recursive call instead of mutating it in place and undoing the change afterward multiplies memory use and makes the backtracking logic harder to follow. Mutate one shared array and subtract the value back out after a failed recursive call.
Edge Cases to Test
Walking through these inputs out loud shows an interviewer that you think about boundaries before they have to ask.
- Empty array
kequal to1kgreater thannums.length- Total sum not divisible by
k - A single element larger than the target sum
- All elements identical
kequal tonums.length, so every subset is one element- Array containing
0values
Additional Considerations
Time and Space Complexity
The backtracking search has a worst-case time complexity of roughly O(k^n), since each of the n elements can, in principle, be tried against each of the k buckets. Processing the largest elements first and skipping symmetric empty buckets cut this down enormously in practice, but the theoretical bound stays exponential.
Space usage is O(n) for the recursion stack plus O(k) for the buckets array, which is small compared to the time cost.
For larger inputs, roughly n up to 15 or 20, a bitmask dynamic programming approach that tracks which subset of elements has already been used, together with the current bucket’s running sum, can be faster in practice because it reuses work across branches instead of exploring every ordering.
Interview Follow-up Questions
An interviewer rarely stops at the base problem. Here are the natural follow-ups, roughly in order of difficulty.
- What if k is always 2? – the problem reduces to the classic equal subset sum partition, solvable with a one-dimensional boolean DP over achievable sums up to
totalSum / 2. - What if n is small, say up to 16, and you want a faster exact solution? – use bitmask DP over all
2^nsubsets, tracking the current bucket’s partial sum for each mask instead of re-exploring orderings through plain backtracking. - What if nums is read-only and cannot be sorted in place? – copy the values into a new array before sorting, or sort an array of indices and read through that instead.
- What if the input arrives as a stream of unknown length? – you cannot answer correctly until you have seen every element, since both the total sum and the full multiset of values are needed, but you can still short-circuit the divisibility check as the running sum updates.
- What if you need the actual subsets, not just a boolean? – record which bucket index each element lands in during the successful backtracking path, instead of only tracking the bucket sums.
Conclusion
Partitioning an array into k equal-sum subsets is a strong example of backtracking with pruning. A few cheap checks, the divisibility test and the largest-element test, eliminate most impossible inputs instantly, and sorting plus the empty-bucket shortcut keep the remaining search manageable.
Try adapting canPartitionKSubsets to return the actual subsets instead of just true or false, or to solve the k = 2 special case with dynamic programming instead of backtracking. You can learn more about array problems like this one in the Arrays category on Daily Java Concept.



