Course4all

Partition to K Equal Sum Subsets

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionWildcard Matching
Next Question →Matchsticks to Square