How do you approach Partition to K Equal Sum Subsets?

The target subset sum is total / k - bail if total is not divisible by k.

What are common mistakes on Partition to K Equal Sum Subsets?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Partition to K Equal Sum Subsets

HardAlgorithms

Description

Given an integer array nums and an integer k, return true if it is possible to divide all elements 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: Subsets (5),(1,4),(2,3),(2,3) each sum to 5.

Example 2

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

Output: false

Explanation: Total 10 is not divisible by 3.

Constraints

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

Partition to K Equal Sum Subsets: approach, complexity and pitfalls

A hard backtracking problem, graded against 10 test cases (8 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

The target subset sum is total / k - bail if total is not divisible by k.
Sort descending and fill one bucket at a time, backtracking when a bucket can't be completed.

The optimal approach

Show the approach: The approach

Backtracking with pruning. If `total % k !== 0` or the largest element exceeds the target, it's impossible. Otherwise fill buckets to `target` one element at a time; when a bucket reaches the target, start the next. Sorting descending and trying larger elements first prunes aggressively.

Time: O(k·2ⁿ) worst case. Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.