Partition of a set into K subsets with equal sum Hard 0 attempts
GeeksforGeeks ↗

Partition of a set into K subsets with equal sum

Hard BacktrackingRecursion GeeksforGeeks

You're given an integer array nums and an integer k. Work out whether the array can be split into k groups, each non-empty, such that every group's elements add up to the same total.

Edge cases: When the overall sum doesn't divide evenly by k, no valid split exists, so return false right away. With k = 1 the whole array is trivially one group, so the answer is always true. If any single element is larger than totalSum / k, it can never fit in a group, so a split is impossible.

Input Format
Implement canPartitionKSubsets(nums, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1,2,3,4]
k = 3
Output
false
Constraints
  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 10^4
Test Cases (2)
Case 1
Args: [[4,3,2,3,5,2,1],4] Expected: true
Case 2
Args: [[1,2,3,4],3] Expected: false
Topics
BacktrackingRecursion

Approach: Backtracking with Pruning

Sort the array in descending order to fail faster. Maintain k buckets — try placing each element into a bucket, and if the bucket sum would exceed the target, skip it. Also skip buckets that have the same current sum as a previously tried bucket (symmetry pruning).

javascript
function canPartitionKSubsets(nums, k) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return false;
  const target = total / k;

  nums.sort((a, b) => b - a);
  if (nums[0] > target) return false;

  const buckets = new Array(k).fill(0);

  function backtrack(idx) {
    if (idx === nums.length) return buckets.every(b => b === target);

    const seen = new Set();
    for (let i = 0; i < k; i++) {
      if (buckets[i] + nums[idx] > target) continue;
      if (seen.has(buckets[i])) continue;
      seen.add(buckets[i]);

      buckets[i] += nums[idx];
      if (backtrack(idx + 1)) return true;
      buckets[i] -= nums[idx];
    }
    return false;
  }

  return backtrack(0);
}

Time Complexity: O(k^n) worst case, but pruning drastically reduces this

Space Complexity: O(n × k) as a loose upper bound for recursion and per-frame symmetry sets

Saved in this browser only. Private to you.

JavaScript