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

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        if batchSize==1:
            return len(groups)
        res = 0
        left = [0]*batchSize
        for g in groups:
            left[g%batchSize]+=1
        # print(f"start left:{left}")
        res+=left[0]
        left[0]=0
        for i,x in enumerate(left):
            # print(f"try ot find pair of {i}")
            if i==(1+batchSize)//2:break 
            if left[i]>0:
                y = left[batchSize-i]
                m = min(x,y)
                res+=m
                left[i]-=m
                left[batchSize-i]-=m
        if batchSize%2==0:
            res+=left[batchSize//2]//2
            left[batchSize//2] = left[batchSize//2]%2
        # print(f"already find {res}, left:{left}")
        @lru_cache(maxsize=None)
        def dfs(left,last):    
            # print(f"dfs of left:{left}, last:{last}")
            if sum(left)==0:return 0        
            ans = -float('inf')
            # for i,x in enumerate(left):
            for i in range(batchSize):
                if left[i]>0:
                    newLeft = list(left)
                    newLeft[i]-=1
                    
                    ans = max(ans,dfs(tuple(newLeft),(last-i)%batchSize)+((last-i)%batchSize==0))
            return ans
        def dfs2(left, last):
            if sum(left) == 0: return 0
            ans = float("-inf")
            for i in range(batchSize):
                if left[i] > 0:
                    t = [j for j in left]
                    t[i] -= 1
                    U = (last - i) % batchSize
                    ans = max(ans, dfs(tuple(t), U) + (U == 0))
                      
            return ans
        return max([res+dfs(tuple(left),x) for x in range(1,batchSize)])
21100