Partition to K Equal Sum Subsets

Problem Statement

Given an integer array nums and an integer k, return true if it is possible to divide the array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true
Explanation: Total = 20, target per subset = 5.
Subsets: {5}, {1,4}, {2,3}, {2,3}

Example 2:

Input: nums = [1, 2, 3, 4], k = 3
Output: false
Explanation: Total = 10, not divisible by 3.

Constraints:

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

Difficulty: Medium (LC 698)

---

Pattern Recognition

• What is the input structure? An array of integers with a partition requirement.
• What are we optimizing? Determining if a valid k-way partition exists.
• What pattern does this fit? Backtracking with pruning. Try to fill k buckets, each with the target sum, using each number exactly once.
• Why does this pattern fit? The problem is NP-complete in general (a variant of bin packing). For small n (up to 16), backtracking with smart pruning or bitmask DP is tractable. The key is aggressive pruning to cut the search space.

---

Approach

Brute Force — Generate All Partitions

Try all possible ways to assign n elements to k groups.

Time: O(k^n) — each of n elements can go into any of k buckets. Space: O(n). Why insufficient: For n=16 and k=4, this is 4^16 ≈ 4 * 10^9. Too slow without pruning.

Optimal — Backtracking with Pruning

Key Insight: Sort the array in descending order and try to fill k buckets each with target sum total / k. The descending sort causes larger numbers to be placed first, which prunes invalid branches earlier. Three critical prunings: (1) skip if sum would exceed target, (2) skip duplicate bucket values, (3) if the largest remaining number exceeds target, return false immediately.

Step-by-step:

1. Compute total = sum(nums). If total % k != 0, return false.
2. Compute target = total / k.
3. Sort nums in descending order.
4. If nums[0] > target, return false (largest element cannot fit in any bucket).
5. Backtrack: try to place each number into one of the k buckets.
   • If a bucket's sum would exceed target, skip.
   • If two buckets have the same current sum, only try one (avoid symmetry).
   • If a bucket reaches exactly target, move to the next number.

function canPartition(nums, k):
    target = sum(nums) / k
    sort nums descending
    buckets = [0] * k
    return backtrack(nums, buckets, 0, target)

function backtrack(nums, buckets, index, target):
    if index == len(nums): return all buckets == target
    seen = set()
    for i in 0..k-1:
        if buckets[i] + nums[index] > target: continue
        if buckets[i] in seen: continue  # Skip duplicate bucket sums
        seen.add(buckets[i])
        buckets[i] += nums[index]
        if backtrack(nums, buckets, index + 1, target): return true
        buckets[i] -= nums[index]
    return false

Time: O(k * 2^n) with pruning — much better in practice than worst case. Space: O(n) for recursion stack.

Alternative — Bitmask DP

For n <= 16, use a bitmask to represent which numbers have been used. dp[mask] tracks whether the subset represented by mask can form some number of complete buckets.

Time: O(n * 2^n). Space: O(2^n).

---

Walkthrough

nums = [4, 3, 2, 3, 5, 2, 1], k = 4
total = 20, target = 5
Sorted descending: [5, 4, 3, 3, 2, 2, 1]

Backtracking trace (abbreviated):

Step	Placing	Into bucket	Buckets state	Action
1	5	B0	[5, 0, 0, 0]	B0 full (= target)
2	4	B1	[5, 4, 0, 0]	Continue
3	3	B1	[5, 7, 0, 0]	7 > 5, backtrack
3	3	B2	[5, 4, 3, 0]	Continue
4	3	B2	[5, 4, 6, 0]	6 > 5, backtrack
4	3	B3	[5, 4, 3, 3]	Continue
5	2	B3	[5, 4, 3, 5]	B3 full
6	2	B2	[5, 4, 5, 5]	B2 full
7	1	B1	[5, 5, 5, 5]	B1 full — all full!

Answer: true — Subsets: {5}, {4,1}, {3,2}, {3,2}.

---

Implementation

TypeScript

function canPartitionKSubsets(nums: number[], k: number): boolean {
    const total = nums.reduce((a, b) => a + b, 0);

    // Quick check: total must be divisible by k
    if (total % k !== 0) return false;

    const target = total / k;

    // Sort descending — place large numbers first for early pruning
    nums.sort((a, b) => b - a);

    // If largest number exceeds target, impossible
    if (nums[0] > target) return false;

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

    function backtrack(index: number): boolean {
        // All numbers placed successfully
        if (index === nums.length) return true;

        const seen = new Set<number>(); // Avoid trying duplicate bucket sums

        for (let i = 0; i < k; i++) {
            // Pruning 1: would exceed target
            if (buckets[i] + nums[index] > target) continue;

            // Pruning 2: skip buckets with the same current sum (symmetry)
            if (seen.has(buckets[i])) continue;
            seen.add(buckets[i]);

            // Place nums[index] in bucket i
            buckets[i] += nums[index];
            if (backtrack(index + 1)) return true;
            buckets[i] -= nums[index];

            // Pruning 3: if bucket was empty and we couldn't fill it,
            // no point trying other empty buckets
            if (buckets[i] === 0) break;
        }

        return false;
    }

    return backtrack(0);
}

C++

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int total = accumulate(nums.begin(), nums.end(), 0);

    // Quick check: total must be divisible by k
    if (total % k != 0) return false;

    int target = total / k;

    // Sort descending — place large numbers first for early pruning
    sort(nums.begin(), nums.end(), greater<int>());

    // If largest number exceeds target, impossible
    if (nums[0] > target) return false;

    vector<int> buckets(k, 0);

    function<bool(int)> backtrack = [&](int index) -> bool {
        // All numbers placed successfully
        if (index == (int)nums.size()) return true;

        unordered_set<int> seen; // Avoid trying duplicate bucket sums

        for (int i = 0; i < k; i++) {
            // Pruning 1: would exceed target
            if (buckets[i] + nums[index] > target) continue;

            // Pruning 2: skip buckets with the same current sum (symmetry)
            if (seen.count(buckets[i])) continue;
            seen.insert(buckets[i]);

            // Place nums[index] in bucket i
            buckets[i] += nums[index];
            if (backtrack(index + 1)) return true;
            buckets[i] -= nums[index];

            // Pruning 3: if bucket was empty and we couldn't fill it,
            // no point trying other empty buckets
            if (buckets[i] == 0) break;
        }

        return false;
    };

    return backtrack(0);
}

Bitmask DP alternative:

TypeScript

function canPartitionKSubsetsBitmask(nums: number[], k: number): boolean {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % k !== 0) return false;

    const target = total / k;
    const n = nums.length;

    // dp[mask] = the remaining sum in the current bucket after filling
    //            as many complete buckets as possible using the numbers in mask
    // -1 means this mask is not achievable
    const dp = new Array(1 << n).fill(-1);
    dp[0] = 0; // No numbers used, no remainder

    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] === -1) continue;
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) continue; // Already used
            const newMask = mask | (1 << i);
            if (dp[newMask] !== -1) continue; // Already found a valid way
            // Current bucket has dp[mask] filled so far
            const newSum = dp[mask] + nums[i];
            if (newSum <= target) {
                dp[newMask] = newSum % target; // Reset to 0 when bucket full
            }
            // If newSum > target, skip (would overflow current bucket)
        }
    }

    return dp[(1 << n) - 1] === 0;
}

C++

bool canPartitionKSubsetsBitmask(vector<int>& nums, int k) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % k != 0) return false;

    int target = total / k;
    int n = nums.size();

    // dp[mask] = the remaining sum in the current bucket after filling
    //            as many complete buckets as possible using the numbers in mask
    // -1 means this mask is not achievable
    vector<int> dp(1 << n, -1);
    dp[0] = 0; // No numbers used, no remainder

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) continue; // Already used
            int newMask = mask | (1 << i);
            if (dp[newMask] != -1) continue; // Already found a valid way
            // Current bucket has dp[mask] filled so far
            int newSum = dp[mask] + nums[i];
            if (newSum <= target) {
                dp[newMask] = newSum % target; // Reset to 0 when bucket full
            }
            // If newSum > target, skip (would overflow current bucket)
        }
    }

    return dp[(1 << n) - 1] == 0;
}

Watch out:

1. Not sorting in descending order. Without this, the backtracking explores many more branches before hitting capacity violations. Descending order forces large numbers first, which prunes early.
2. Missing the symmetry pruning. If two buckets have the same current sum, placing a number in either yields the same future states. Skipping duplicates avoids redundant exploration — this is the single most impactful optimization.
3. Bitmask DP: using new_sum > target check. Without this, you might "overfill" a bucket, leading to wrong results. The new_sum % target only works when new_sum == target; for new_sum > target, the number simply cannot go into this bucket.

---

Complexity Analysis

	Time	Space
Brute Force	O(k^n)	O(n)
Backtracking + Pruning	O(k * 2^n) worst case	O(n)
Bitmask DP	O(n * 2^n)	O(2^n)

Bottleneck: For n = 16, the bitmask DP explores 16 * 2^16 = ~10^6 states — very fast. The backtracking approach with good pruning is also fast in practice but has a worse theoretical bound. The trade-off is space: bitmask DP uses O(2^16) = 65,536 entries, while backtracking uses O(n) stack space.

---

Edge Cases

1. k = 1 — Always true if the array is non-empty. The entire array forms one subset.
2. k = n — Each number must equal target = total / n. Return true only if all numbers are equal.
3. Total not divisible by k — Return false immediately.
4. Largest number > target — Return false immediately. No bucket can hold it.
5. All elements equal — If n % k == 0, return true. Otherwise false.
6. n = 1, k = 1 — Trivially true.

---

Related Problems

• LC 416 — Partition Equal Subset Sum — Special case with k=2. Solvable with subset-sum DP in O(n * target).
• LC 473 — Matchsticks to Square — Partition into k=4 subsets with equal sum. Same backtracking approach.
• LC 1986 — Minimum Number of Work Sessions — Bitmask DP on task assignments. Same state representation.
• LC 2305 — Fair Distribution of Cookies — Backtracking to distribute items into k groups, minimizing the maximum sum.

---

What is Expected at Each Level

Junior: Recognize the problem is about partitioning. Write the brute-force backtracking without optimizations. May not consider the divisibility check or sorting.

Mid-level: Add all three pruning optimizations (sort descending, skip duplicate bucket sums, early termination on empty bucket). Discuss the divisibility quick check. Implement cleanly and analyze complexity.

Senior: Implement both the backtracking and bitmask DP approaches. Compare their trade-offs (time vs space, practical speed vs theoretical bound). Extend to the optimization variant: "Minimize the maximum subset sum given k partitions." Discuss connections to bin packing and job scheduling.