<p>There is a donuts shop that bakes donuts in batches of <code>batchSize</code>. They have a rule where they must serve <strong>all</strong> of the donuts of a batch before serving any donuts of the next batch. You are given an integer <code>batchSize</code> and an integer array <code>groups</code>, where <code>groups[i]</code> denotes that there is a group of <code>groups[i]</code> customers that will visit the shop. Each customer will get exactly one donut.</p>

<p>When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.</p>

<p>You can freely rearrange the ordering of the groups. Return <em>the <strong>maximum</strong> possible number of happy groups after rearranging the groups.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> batchSize = 3, groups = [1,2,3,4,5,6]
<strong>Output:</strong> 4
<strong>Explanation:</strong> You can arrange the groups as [6,2,4,5,1,3]. Then the 1<sup>st</sup>, 2<sup>nd</sup>, 4<sup>th</sup>, and 6<sup>th</sup> groups will be happy.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> batchSize = 4, groups = [1,3,2,5,2,2,1,6]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= batchSize &lt;= 9</code></li>
	<li><code>1 &lt;= groups.length &lt;= 30</code></li>
	<li><code>1 &lt;= groups[i] &lt;= 10<sup>9</sup></code></li>
</ul>

from typing import List

def get_combinations(
    counts: list[int], i: int, current: list[int], answer: list[list[int]]
):
    if i == len(counts):
        answer.append(current.copy())
        return
    for j in range(counts[i] + 1):
        current[i] = j
        get_combinations(counts, i + 1, current, answer)
    current[i] = 0

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        # i guess the naive way is just try every permutation?
        # 9 distinct numbers
        # up to 30 places

        # looks like we want to create matches
        # 1 2 3 4 5 6 -> 1 2 0 1 2 0 -> 0 0 1 2 1 2

        # 1 3 2 5 2 2 1 6
        # mod 4
        # 1 3 2 1 2 2 1 2
        # 1 3 2 2 2 2 1 1
        # 1   1   1   1

        # 3 3 3 3
        # mod 4
        # 3 3 3 3
        # 1

        counts = [0 for _ in range(batchSize)]
        for num in groups:
            counts[num % batchSize] += 1

        # start by preprocessing to get rid of all good groups
        ret = counts[0]
        counts[0] = 0
        for i in range(1, batchSize):
            if i != batchSize - i:
                n_happy = min(counts[i], counts[batchSize - i])
            else:
                n_happy = counts[i] // 2
            ret += n_happy
            counts[i] -= n_happy
            counts[batchSize - i] -= n_happy

        combinations = []
        get_combinations(counts, 0, [0]*len(counts), combinations)
        m = {
            tuple(comb):0
            for comb in combinations
        }

        for comb in combinations[1:]:
            # had to have come from one of the previous
            best = 0
            for i in range(len(counts)):
                if comb[i] > 0:
                    comb[i] -= 1
                    tmp = tuple(comb)
                    v = m[tmp]
                    v += 1 if sum([comb[j]*j for j in range(len(comb))]) % batchSize == 0 else 0
                    comb[i] += 1
                    best = max(best, v)
            m[tuple(comb)] = best

        return ret + max(m.values())

16800