464. Partition to K Equal Sum Subsets
You receive an array of positive integers nums and an integer k. Decide whether the whole array can be split into exactly k non-empty groups whose sums are all equal. Every element must land in exactly one group.
Return true if such a split exists and false otherwise. Print the answer in lowercase: true or false.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true
Explanation: The total is 20, so each of the 4 groups must sum to 5: (5), (1, 4), (2, 3), (2, 3).
Example 2:
Input: nums = [1, 2, 3, 4], k = 3
Output: false
Explanation: The total is 10, which is not divisible by 3, so equal groups are impossible.
Constraints:
- 1 ≤ k ≤ nums.length ≤ 16
- 1 ≤ nums[i] ≤ 10⁴
- The frequency of each element is at most 4.
Hints:
If the total sum is not divisible by k, or any single element exceeds sum/k, you can answer false immediately. Otherwise each group must sum to exactly target = sum/k.
Backtracking: keep k running bucket sums and try to place each element into a bucket that stays ≤ target. Place the largest elements first, and never try two buckets that currently hold the same sum — they are interchangeable.
n ≤ 16 invites a bitmask: represent the set of used elements as a 16-bit mask and remember, for each reachable mask, how full the current (partial) group is. If the full mask is reachable with the last group closed, the answer is true.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Expected output: true