Partition to K Equal Sum Subsets

Explanation & Solution

Description

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

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

Output: true

Explanation: It is possible to divide the array into 4 subsets: [5], [1,4], [2,3], [2,3] with equal sum 5.

Constraints

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

Approach

Subsets pattern

1. Check Divisibility

Compute the total sum of all elements.
If totalSum % k !== 0, it is impossible to partition into k equal subsets — return false.
Otherwise, each subset must have a target sum of totalSum / k.

2. Sort in Descending Order

Sort nums in descending order.
If the largest element exceeds the target, return false immediately.
Sorting helps prune the search tree earlier by trying larger numbers first.

3. Backtracking with Buckets

Use a used array to track which elements have been placed in a bucket.
Recursively try to fill one bucket at a time to the target sum.
Once a bucket reaches the target, start filling the next bucket from index 0.

4. Pruning Strategies

Skip used elements: Don't reuse already-placed numbers.
Skip overflow: If adding nums[i] exceeds the target, skip it.
Skip duplicates: If the previous identical element was not used, skip the current one to avoid exploring equivalent states.

5. Base Case

When all k buckets are successfully filled (bucketsLeft === 0), return true.
If no valid placement is found for any bucket, backtrack and return false.

Key Insight

This is an NP-hard problem (subset-sum variant), but with n <= 16, backtracking with smart pruning is efficient enough.
Sorting descending and pruning duplicates dramatically reduces the search space.

Time

O(k * 2^n) in the worst case.

Space

O(n) for the recursion stack and used array.

Visualization

Input:

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

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Count Number of Maximum Bitwise-OR Subsets

Target Sum