Partition of a set into K subsets with equal sum | Problems

Given an integer array nums and an integer k, return true if you can divide the array into k non-empty subsets that all have the same sum.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true
Explanation: Total sum is 20. Each subset must sum to 5: [5], [4,1], [3,2], [3,2].

Example 2:

Input: nums = [1, 2, 3, 4], k = 3
Output: false

Edge cases: If total sum isn't divisible by k, immediately return false. k = 1 is always true. Any single element exceeding totalSum / k makes it impossible.

Sample Input

nums = [4, 3, 2, 3, 5, 2, 1], k = 4

Sample Output

true

Constraints

1 <= k <= nums.length <= 16
1 <= nums[i] <= 10^4

Test Cases

Case 1

Args: [[4,3,2,3,5,2,1],4] Expected: true

Topics

Backtracking Recursion

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).

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) for recursion stack

Saved in this browser only. Private to you.