Partition to K Equal Sum Subsets
Medium Backtracking with pruning
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether the array can be split into k groups that all have the same sum.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can the numbers be split into k groups with equal sums?
Why this works: each group must hit total / k. Place the largest numbers first into buckets and backtrack on failure; skip buckets that look the same.
Example: [4, 3, 2, 3, 5, 2, 1], k = 4 → target 5
5 | 4+1 | 3+2 | 3+2 ✓✦Hints open one at a time
↗Approach
Sort descending. Recursively assign each number to a bucket whose sum stays within the target. Prune: skip buckets with the same current sum as one already tried, and stop after trying an empty bucket.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int total = 0;
for (int x : nums) total += x;
if (total % k != 0) return false;
Arrays.sort(nums);
int target = total / k;
if (nums[nums.length - 1] > target) return false;
return place(nums, nums.length - 1, new int[k], target); // largest first
}
private boolean place(int[] nums, int i, int[] bucket, int target) {
if (i < 0) return true; // every number placed
for (int b = 0; b < bucket.length; b++) {
if (bucket[b] + nums[i] > target) continue;
if (b > 0 && bucket[b] == bucket[b - 1]) continue; // same state as a bucket already tried
bucket[b] += nums[i];
if (place(nums, i - 1, bucket, target)) return true;
bucket[b] -= nums[i];
if (bucket[b] == 0) break; // failed in an empty bucket: no other empty bucket helps
}
return false;
}
}!Common mistake
Not sorting in descending order — big numbers placed last cause much more backtracking.
- Time: O(k^n) worst case, far less with pruning.
- Space: O(n).