<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 collections import defaultdict
from functools import lru_cache
from typing import List

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        count = [0] * batchSize
        # Count the number of groups for each remainder mod batchSize
        for group in groups:
            remainder = group % batchSize
            count[remainder] += 1
        
        # Initial number of happy groups
        happy = count[0]
        
        # Try to pair groups whose remainders sum up to batchSize
        for i in range(1, (batchSize + 1) // 2):
            complement = batchSize - i
            pairs = min(count[i], count[complement])
            happy += pairs
            count[i] -= pairs
            count[complement] -= pairs
        
        # For the middle element when batchSize is even (e.g., batchSize = 4, i.e., consider count[2])
        if batchSize % 2 == 0:
            happy += count[batchSize // 2] // 2
            count[batchSize // 2] %= 2
        
        @lru_cache(None)
        def dp(remaining_count):
            max_happy = 0
            total_sum = sum(i * remaining_count[i] for i in range(batchSize))
            for i in range(1, batchSize):
                if remaining_count[i] > 0:
                    new_count = list(remaining_count)
                    new_count[i] -= 1
                    add_happy = int(total_sum % batchSize == i)
                    max_happy = max(max_happy, dp(tuple(new_count)) + add_happy)
            return max_happy
        
        # Use DP to calculate the maximum number of happy groups
        result = happy + dp(tuple(count))
        return result

# Example usage:
sol = Solution()
print(sol.maxHappyGroups(3, [1, 2, 3, 4, 5, 6]))  # Output: 4
print(sol.maxHappyGroups(4, [1, 3, 2, 5, 2, 2, 1, 6]))  # Output: 4
17100