<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: int, groups: list[int]) -> int:
        # Step 1: Calculate the remainder for each group when divided by batchSize
        group_remainders = [g % batchSize for g in groups]
        
        # Step 2: Dictionary to store count of groups by remainder
        remainder_count = Counter(group_remainders)
        
        # Step 3: Handle groups that are happy by default (remainder 0)
        happy_groups = remainder_count[0]
        remainder_count[0] = 0  # Clear remainder 0 as they are already accounted for
        
        # Step 4: Pre-process complementary group pairs (those that sum to batchSize)
        for rem in range(1, batchSize):
            complementary_rem = batchSize - rem
            if rem != complementary_rem:  # Pair different remainders
                pairs = min(remainder_count[rem], remainder_count[complementary_rem])
                happy_groups += pairs
                remainder_count[rem] -= pairs
                remainder_count[complementary_rem] -= pairs
            else:  # Handle the case where remainder is equal to batchSize/2 (like 2+2=4 in batchSize=4)
                happy_groups += remainder_count[rem] // 2
                remainder_count[rem] %= 2
        
        # Step 5: Gather remaining unpaired groups for the DP step
        remaining_groups = []
        for r, count in remainder_count.items():
            remaining_groups.extend([r] * count)  # Add each remainder 'r' 'count' times
        
        # Step 6: If no unpaired groups are left, return happy groups
        if not remaining_groups:
            return happy_groups
        
        # Step 7: Setup DP with bitmasking to solve remaining groups
        N = len(remaining_groups)
        target_mask = (1 << N) - 1  # All groups are served when all bits are 1

        # Memoization table for the DP
        memo = {}

        # Step 8: DP function to find the maximum number of happy groups
        def dp(mask, current_remainder):
            """
            Recursively calculates the maximum number of happy groups using a bitmask.
            Args:
            - mask: a bitmask indicating which groups have already been served.
            - current_remainder: the number of leftover donuts from the previous group.
            
            Returns:
            - Maximum number of happy groups achievable from the current state.
            """
            if mask == target_mask:
                return 0  # All groups served, no more happy groups can be added.
            
            if (mask, current_remainder) in memo:
                return memo[(mask, current_remainder)]

            max_happy = 0
            current_remainder %= batchSize
            bonus_happy = 1 if current_remainder == 0 else 0  # If no leftover donuts, the next group is happy

            seen_groups = set()  # To avoid trying the same remainder more than once in this state

            # Step 9: Try to serve each unserved group
            for i in range(N):
                if (mask & (1 << i)) == 0 and remaining_groups[i] not in seen_groups:
                    seen_groups.add(remaining_groups[i])
                    
                    # Update the mask to mark group 'i' as served and calculate the new remainder
                    new_mask = mask | (1 << i)
                    new_remainder = current_remainder + remaining_groups[i]
                    
                    # Recursively solve for the new state
                    max_happy = max(max_happy, dp(new_mask, new_remainder) + bonus_happy)

            memo[(mask, current_remainder)] = max_happy
            return max_happy
        
        # Step 10: Start the DP process with all groups unserved and no leftover donuts
        return happy_groups + dp(0, 0)

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        N = len(groups)

        # We only need to worry about the non-zero remainder
        groups = [i % batchSize for i in groups if i % batchSize]

        # Can already be satisfied
        satisfied = N - len(groups)

        # For those groups that complement each other, we can only satisfy one group
        matching = defaultdict(int)
        for group in groups:
            if matching[batchSize - group] > 0:
                matching[batchSize - group] -= 1
                satisfied += 1
            else:
                matching[group] += 1

        groups = []
        for group, count in matching.items():
            groups += [group] * count

        # Brute force the rest
        @lru_cache(None)
        def allocate(leftOver: int, groups: tuple) -> int:
            if not groups:
                return 0

            result = 0
            for i in range(len(groups)):
                nextGroups = groups[0: i] + groups[i + 1:]
                nextLeftOver = (leftOver - groups[i]) % batchSize
                result = max(result, allocate(nextLeftOver, nextGroups) + int(leftOver == 0))

            return result

        return allocate(0, tuple(groups)) + satisfied
17500