698. Partition to K Equal Sum Subsets

698

MediumBacktrackingBacktracking filling k buckets to a target sumk equal-sum subsets backtracking with used mask and pruning

Partition to K Equal Sum Subsets

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

Open official problem prompt ↗

In plain English

Decide whether all elements can be partitioned into k groups that each add up to total/k.

Picture it like this

Like dealing cards into k piles so every pile has the same point total; you fill one pile to the goal, then move on to the next, backtracking whenever a pile cannot be completed.

Example

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Why: The total is 20, so each subset must sum to 5: (5), (1,4), (2,3), and (2,3) are four equal-sum subsets using every element.

Constraints

1 <= k <= nums.length <= 161 <= nums[i] <= 10^4The sum of all nums does not exceed 2^31 - 1

Pattern lesson

See the pattern, then code

k equal-sum subsets backtracking with used mask and pruning

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Sort descending, fill one subset up to the target, and when it is exactly full recurse to build the next subset, using a used array and start index to avoid re-picking and reordering.

New words, made simpleKnow these before the algorithm

Target sum: total/k, the required sum of each of the k subsets.
used array: Booleans marking which elements are already committed to a subset.
Subset completion: Reaching cur_sum == target, which locks a subset and starts the next one.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all subset assignments

Explodes combinatorially and repeats symmetric group orderings.

Assign each element to one of k groups and verify equal sums.

Time O(k^n)Space O(n)

Best choiceFill one subset at a time with pruning

Sorting descending plus pruning keeps it tractable for n up to 16.

Complete subsets sequentially; skip used or overflowing elements and prune symmetric empty-subset starts.

Time O(k * 2^n)Space O(n)

The rule we keep true

Invariant

Elements marked used belong to already-completed or in-progress subsets; cur_sum is the running sum of the subset currently being built and never exceeds target.

Why this is correct

Reasoning

Each completed subset sums to exactly target, and completing k of them consumes all elements because k*target equals the total. Filling subsets one at a time with a start index avoids duplicate orderings, and skipping overflowing elements keeps every subset valid.

The algorithm in three movesSay these aloud before coding

1Return false unless total is divisible by k and max element fits the target

target = 20/4 = 5

2Sort descending and track a used flag per element

subset1={5}, subset2={4,1}

3Add unused elements from a start index without exceeding the target

subset3={3,2}, subset4={3,2} -> true

4When cur_sum hits target, decrement k and restart from index 0 for the next subset

5Prune symmetric branches when cur_sum is 0 and a placement fails

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read[4,3,2,3,5,2,1], k=4

2 · AskDivisible by k? Max fits?

3 · Update statetotal=20, target=5, sorted=[5,4,3,3,2,2,1]

4 · ResultProceed

Key takeaway

Elements sorted descending; the lone 5 immediately forms one complete subset.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-9Feasibility and sort
Reject non-divisible totals or an oversized element; sort descending so large elements are placed first.
2
Lines 12-15Subset boundaries
k_remaining==0 means success; a full subset resets cur_sum and starts the next subset from index 0.
3
Lines 16-25Pick with pruning
Skip used or overflowing elements; on failure undo, and break when cur_sum is 0 to prune symmetric starts.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k equal to nums.length requires every element to equal the target
Total not divisible by k returns false
Any single element exceeding target returns false
k == 1 always true since the whole array is one subset

Common beginner mistakes

Recursing from i instead of i+1, reusing an element within a subset
Not resetting start to 0 when a subset completes
Omitting the cur_sum==0 break, losing a major prune
Forgetting to mark and unmark used, corrupting other branches

Check your understanding

Why restart the next subset from index 0 rather than continuing from the current index?

PyPython 3 · solution.py

Optimal

1class Solution:2    def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:3        total = sum(nums)4        if total % k != 0:5            return False6        target = total // k7        nums.sort(reverse=True)8        if nums[0] > target:9            return False10        used = [False] * len(nums)1112        def backtrack(start: int, k_remaining: int, cur_sum: int) -> bool:13            if k_remaining == 0:14                return True15            if cur_sum == target:16                return backtrack(0, k_remaining - 1, 0)17            for i in range(start, len(nums)):18                if used[i] or cur_sum + nums[i] > target:19                    continue20                used[i] = True21                if backtrack(i + 1, k_remaining, cur_sum + nums[i]):22                    return True23                used[i] = False24                if cur_sum == 0:25                    break26            return False2728        return backtrack(0, k, 0)

Time complexityO(k * 2^n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaMicrosoft

Partition to K Equal Sum Subsets

Partition to K Equal Sum Subsets

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking