<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, groups):
        ans = sum([1 for i in groups if i%batchSize == 0])
        groups = sorted([i%batchSize for i in groups if i%batchSize != 0])

        @lru_cache(None)
        def dfs(total,groups):
            if not groups: return 0

            max_val = 0

            for i in range(len(groups)):
                max_val = max(max_val,dfs(total + groups[i],groups[:i] + groups[i+1:]))

            return max_val + (total%batchSize == 0)

        return ans + dfs(0,tuple(groups))

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        groups = [v % batchSize for v in groups]
        mp = {}
        ans = 0

        for g in groups:
            if g == 0:
                ans += 1
            else:
                if batchSize - g in mp:
                    ans += 1
                    mp[batchSize - g] -= 1
                    if mp[batchSize - g] == 0:
                        del mp[batchSize - g]
                else:
                    if g not in mp:
                        mp[g] = 0
                    mp[g] += 1

        new_groups = []
        for k in mp:
            new_groups += [k] * mp[k]

        N = len(new_groups)
        target = (1 << N) - 1

        @cache
        def solve(mask, cur):
            if mask == target:
                return 0

            best, tmp = 0, 0
            cur %= batchSize

            if cur == 0:
                tmp = 1

            seen = set()

            for i in range(N):
                if (mask & (1 << i)) == 0 and new_groups[i] not in seen:
                    seen.add(new_groups[i])
                    
                    rem = (cur + new_groups[i]) % batchSize
                    
                    best = max(best, solve(mask | (1 << i), cur + new_groups[i]))

                    if rem == 0:
                        return (cur == 0) + best

            return best + (cur == 0)

        return solve(0, 0) + ans
17200