698. Partition to K Equal Sum Subsets

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: Medium
LeetCode: 698

Quick Sights

Time Complexity: O(number of states * cost per state); output-heavy problems are bounded by the number of generated states.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Partition nums into exactly k non-empty subsets with equal sum (each subset sums to total/k). Return whether possible.

Concept Explanation

Partition nums into exactly k non-empty subsets with equal sum (each subset sums to total/k). Return whether possible.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Target subset sum known if total % k == 0
NP-complete flavor — use backtracking with buckets or bitmask memo in optimized variants
Sort descending to prune faster

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute — partition enumeration — infeasible.
Better — DFS assign each number to one of k buckets tracking current sums — backtracking with pruning.
Memoization — bitmask state (mask, bucketIndex) optional acceleration.

Optimal Solution

Go

import "sort"

func canPartitionKSubsets(nums []int, buckets int) bool {
	total := 0
	for _, value := range nums {
		total += value
	}
	if total% buckets != 0 {
		return false
	}
	target := total / buckets
	sort.Slice(nums, func(left, right int) bool {
		return nums[left] > nums[right]
	})
	bucketSums := make([]int, buckets)

	var dfs func(index int) bool
	dfs = func(index int) bool {
		if index == len(nums) {
			return true
		}
		value := nums[index]
		for bucketIndex := 0; bucketIndex < buckets; bucketIndex++ {
			if bucketSums[bucketIndex]+value > target {
				continue
			}
			bucketSums[bucketIndex] += value
			if dfs(index + 1) {
				return true
			}
			bucketSums[bucketIndex] -= value
			if bucketSums[bucketIndex] == 0 {
				break
			}
		}
		return false
	}
	return dfs(0)
}

JavaScript

function canPartitionKSubsets(nums, bucketCount) {
  const total = nums.reduce((sum, value) => sum + value, 0);
  if (total % bucketCount !== 0) {
    return false;
  }
  const target = total / bucketCount;
  nums.sort((left, right) => right - left);
  const bucketSums = new Array(bucketCount).fill(0);

  function dfs(index) {
    if (index === nums.length) {
      return true;
    }
    const value = nums[index];
    for (let bucketIndex = 0; bucketIndex < bucketCount; bucketIndex += 1) {
      if (bucketSums[bucketIndex] + value > target) {
        continue;
      }
      bucketSums[bucketIndex] += value;
      if (dfs(index + 1)) {
        return true;
      }
      bucketSums[bucketIndex] -= value;
      if (bucketSums[bucketIndex] === 0) {
        break;
      }
    }
    return false;
  }

  return dfs(0);
}

Walkthrough

If total % k != 0, immediate false. Else fill buckets greedily with largest-first DFS.

Invariant: Each recursion places nums[index] into some bucket without exceeding target; symmetry pruning skips empty bucket repeats.

Edge Cases

k == 1 — always true if sum consistent
Single element equal to target
Impossible remainder — total % k != 0

Pitfalls

Ascending sort — weaker pruning
Not breaking when bucket empty trial fails — duplicate symmetric work

Variants

K equal sum subsets with multiset — same backtracking, stronger dedupe.
Minimize largest bucket sum — becomes different problem (see split array largest sum / binary search on answer).

Mind-Map Tags

#backtracking #bucket-fill #pruning #sort-desc #bitmask-optional