<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 Counter

class Solution:
    def maxHappyGroups(self, batchSize, groups):
        # Step 1: Count the number of groups by their remainder when divided by batchSize
        remainders = [g % batchSize for g in groups]
        remainder_count = Counter(remainders)
        
        # Step 2: Remove groups that have remainder 0 (happy by default)
        happy_groups = remainder_count[0]
        remainder_count[0] = 0
        
        # Step 3: Memoization table (dictionary)
        memo = {}

        # Step 4: DP function with memoization
        def dp(state, rem):
            """
            Dynamic programming function to maximize the number of happy groups.
            
            Args:
            - state: a tuple representing the remaining count of groups by their remainder.
            - rem: the current remainder of the donuts left from the previous group.
            
            Returns:
            - The maximum number of happy groups.
            """
            # If all groups are processed, return 0
            if sum(state) == 0:
                return 0
            
            # Check if this state has already been computed
            if (state, rem) in memo:
                return memo[(state, rem)]
            
            # Try all group types (remainders) to serve next
            max_happy = 0
            for i in range(1, batchSize):
                if state[i] > 0:  # If there are groups with remainder i left
                    # Create a new state by reducing the count of remainder i groups
                    new_state = list(state)
                    new_state[i] -= 1
                    new_rem = (rem + i) % batchSize  # Update remainder for the next group
                    
                    # If the current remainder is 0, the next group will be happy
                    happy = 1 if rem == 0 else 0
                    max_happy = max(max_happy, happy + dp(tuple(new_state), new_rem))
            
            # Save the result in memo table before returning
            memo[(state, rem)] = max_happy
            return max_happy

        # Step 5: Convert the remainder_count into a tuple to represent the initial state
        state = tuple(remainder_count[i] for i in range(batchSize))
        
        # Step 6: Start the DP from the initial state with a remainder of 0
        return happy_groups + dp(state, 0)
70100