---
description: Greedy+DFS
---

# LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts

There is a donuts shop that bakes donuts in batches of `batchSize`. They have a rule where they must serve **all** of the donuts of a batch before serving any donuts of the next batch. You are given an integer `batchSize` and an integer array `groups`, where `groups[i]` denotes that there is a group of `groups[i]` customers that will visit the shop. Each customer will get exactly one donut.

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.

You can freely rearrange the ordering of the groups. Return _the **maximum** possible number of happy groups after rearranging the groups._

**Example 1:**

```
Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.
```

**Example 2:**

```
Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]
Output: 4
```

**Constraints:**

* `1 <= batchSize <= 9`
* `1 <= groups.length <= 30`
* `1 <= groups[i] <= 10^9`

## Solution

[English Version in Youtube](https://youtu.be/h7U1S7Ut3ws)

[中文版解答Youtube Link](https://youtu.be/0FduysByEmE)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1Ly4y1b7bq/)

```
class Solution {
public:
    string GetKey(const vector<int>& cnts) {
        stringstream ss;
        for (int i = 1; i < cnts.size(); i++) {
            ss << i << ":" << cnts[i] << ":";
        }
        return ss.str();
    }
    
    int dfs(vector<int>& cnts, int remain, int batchSize, unordered_map<string, int>& cache) {
        string key = GetKey(cnts);
        if (cache.count(key) > 0) {
            return cache[key];
        }
        
        int res = 0;
        for (int i = 1; i < cnts.size(); i++) {
            if (cnts[i] == 0) continue;
            
            int tmp = (remain == 0 ? 1 : 0);
            cnts[i]--;
            tmp += dfs(cnts, (remain - i + batchSize) % batchSize, batchSize, cache);
            cnts[i]++;
            res = max(res, tmp);
        }
        return cache[key] = res;
    }
    
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        int res = 0;
        vector<int> cnts(batchSize, 0);
        for (int group : groups) {
            int g = group % batchSize;
            if (g == 0) {
                res++;
            } else if (cnts[batchSize - g] > 0) {
                res++;
                cnts[batchSize - g]--;
            } else {
                cnts[g]++;
            }
        }
        
        // batchSize = 4, groups = [1,3,2,5,2,2,1,6]
        // cnts = [0, 3, 4, 1] -> [0, 2, 0, 0] res = 3
        unordered_map<string, int> cache;
        return res + dfs(cnts, /*remain=*/0, batchSize, cache);
    }
};
```
