Partition to K Equal Sum Subsets

The key idea

Each subset must sum to total / k. If that target is not a whole number, or any single element exceeds it, the answer is immediately false. Otherwise fill one bucket at a time with backtracking, sorting elements large-first so dead ends are reached sooner.

Problem

You are given an integer array nums and a positive integer k. Decide whether it is possible to divide nums into k non-empty subsets whose sums are all equal.

Every element of nums must belong to exactly one subset, and every one of the k subsets must be used. Return true if such a partition exists and false otherwise.

Constraints

1 <= k <= nums.length <= 16
0 < nums[i] < 10^4
The frequency of each element is in the range [1, 4].

Examples

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

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →