Course4all
Join us on telegram
Home/dsa/Backtracking/Partition to K Equal Sum Subsets

Partition to K Equal Sum Subsets

Master this topic with zero to advance depth.

Partition to K Equal Sum Subsets

Filling the Buckets

We need to divide NN numbers into KK groups, where each group has the same sum. This target sum is TotalSum / K.

Pruning Strategies (Crucial for Hard)

  1. If TotalSum is not divisible by KK, return False immediately.
  2. Sort nums in descending order to fill buckets with larger numbers first (fails faster on impossible branches).
  3. If a bucket cannot take the current number and it's the first number in the bucket, skip because further search will fail too.

Partition an array into K subsets of equal sum. Includes visual bucket-filling trace.

Hard

Examples

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

Level I: Backtracking (Optimized with Sorting)

Intuition

Try putting each number into each of the K buckets.

To optimize, we sort descending. In each step, we iterate through K buckets. If bucket[j] + nums[idx] <= target, we add it and recurse. If we hit the end, success.

⏱ O(K^N)💾 O(N)

Detailed Dry Run

nums=[5,4,3,2,1], target=5, k=3 1. Pick 5: Add to B1 (5). OK. 2. Pick 4: Add to B2 (4). OK. 3. Pick 3: B1(8)>5 (❌), B2(7)>5 (❌), B3(3). OK. 4. Pick 2: B1(5) (❌ skip), B2(6) (❌), B3(5). OK.
java
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums);
        int[] buckets = new int[k];
        return backtrack(nums.length - 1, nums, buckets, target);
    }
    private boolean backtrack(int idx, int[] nums, int[] buckets, int target) {
        if (idx == -1) return true;
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + nums[idx] <= target) {
                buckets[i] += nums[idx];
                if (backtrack(idx - 1, nums, buckets, target)) return true;
                buckets[i] -= nums[idx];
            }
            if (buckets[i] == 0) break; // Pruning: first time bucket empty
        }
        return false;
    }
}
← Previous QuestionWildcard Matching
Next Question →Matchsticks to Square