DSA problem
Partition to K Equal Sum Subsets
Given an integer array nums and a positive integer k, determine whether it is possible to partition nums into exactly k non-empty subsets whose sums are all equal. Return true if such a partition exists and false otherwise.
The simple invariants come first: the total sum must be divisible by k, and the largest element must not exceed the per-subset target total / k. If either check fails, return false immediately. Otherwise we need to decide whether the elements can be packed into k boxes of size target.
A bitmask DP works cleanly for n <= 16. Let mask be a bitset of which elements have been used so far and let used be the cumulative sum of those elements. Define dp[mask] = used % target if mask is reachable, or -1 otherwise. Whenever we add an element i to a reachable mask, the new partial sum modulo target must not "overflow" the current subset — equivalently, nums[i] <= target - dp[mask]. When dp[mask] + nums[i] is exactly target, we have just closed off a subset and the next addition starts a fresh box, encoded by the residue rolling back to zero.
The answer is dp[(1 << n) - 1] == 0, meaning every element is used and the residue is exactly on a subset boundary. The total work is O(2^n * n), which is at most 2^{16} * 16 ≈ 10^6. An alternative for slightly larger n is sorted backtracking with pruning, but bitmask DP is the cleanest production solution here.
Examples
nums = [4,3,2,3,5,2,1], k = 4truenums = [1,2,3,4], k = 3falsenums = [2,2,2,2,3,4,5], k = 4falseConstraints
- 1 <= k <= nums.length <= 16
- 1 <= nums[i] <= 10^4
- The frequency of each element is in the range [1, 4].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.