584. Can It Be Split Into k Equal Groups
Given n positive numbers and an integer k, decide whether they can be split into exactly
k groups whose sums are all equal. Every number goes into exactly one group.
Print Yes or No.
5 numbers 3 1 4 2 2, k = 2 -> Yes {3,1,2} and {4,2}
5 numbers 1 1 1 1 4, k = 2 -> Yes {4} and {1,1,1,1}
6 numbers 1 1 1 1 1 5, k = 3 -> No
## Two rejections before any work
If the total is not divisible by k, the answer is No. If any single number exceeds
total / k, it cannot fit in any group, so the answer is No.
Both are worth doing first, because they remove most inputs for free and because they
guarantee target >= 1 for the step below, which relies on it.
## One number per mask
The obvious state carries a list of k partial sums, which is far too much. Collapse it by
filling the groups ONE AT A TIME, in order:
f[mask] = the load of the group currently being filled, after using exactly the items in mask
Because groups are filled in sequence, every completed group holds exactly target, so the
total used is popcount-independent: it is determined by mask alone. The only thing left to
remember is how far along the CURRENT group is, and that is one number.
f[0] = 0
for i not in mask, if f[mask] + a[i] <= target:
f[mask | (1<<i)] = (f[mask] + a[i]) % target
The remainder is what rolls over to the next group: a load that reaches exactly target wraps
to 0, which starts a fresh group without any extra index.
The answer is Yes exactly when f[full] is reachable and equal to 0.
## Reachable is not the same as zero
f[mask] = 0 is a legitimate value, so the table cannot use 0 to mean unreachable. Keep a
separate flag, or use -1 as the sentinel.
Conflating the two is the bug this problem is built around, and it reports Yes on inputs
where nothing is reachable at all.
## Why the first value found is safe to keep
Each mask is written once, with whatever load the first successful route produced. That is
enough because the total used is fixed by mask, so every route to the same mask leaves the
current group at the SAME load. There is nothing to compare and nothing to improve.
## The empty group question
Every number is at least 1, so target >= 1, so no group can be empty. That is why the
constraint excludes zero, and it is what makes "exactly k groups" need no separate check.
## Cost
Time O(2^n * n). Space O(2^n).
Constraints - `1 ≤ n ≤ 16` - `1 ≤ k ≤ n` - `1 ≤ each number ≤ 1000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.