Formatted question description: https://leetcode.ca/all/2305.html

# 2305. Fair Distribution of Cookies (Medium)

You are given an integer array `cookies`

, where `cookies[i]`

denotes the number of cookies in the `i`

bag. You are also given an integer ^{th}`k`

that denotes the number of children to distribute **all** the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.

The **unfairness** of a distribution is defined as the **maximum** **total** cookies obtained by a single child in the distribution.

Return *the minimum unfairness of all distributions*.

**Example 1:**

Input:cookies = [8,15,10,20,8], k = 2Output:31Explanation:One optimal distribution is [8,15,8] and [10,20] - The 1^{st}child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies. - The 2^{nd}child receives [10,20] which has a total of 10 + 20 = 30 cookies. The unfairness of the distribution is max(31,30) = 31. It can be shown that there is no distribution with an unfairness less than 31.

**Example 2:**

Input:cookies = [6,1,3,2,2,4,1,2], k = 3Output:7Explanation:One optimal distribution is [6,1], [3,2,2], and [4,1,2] - The 1^{st}child receives [6,1] which has a total of 6 + 1 = 7 cookies. - The 2^{nd}child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies. - The 3^{rd}child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies. The unfairness of the distribution is max(7,7,7) = 7. It can be shown that there is no distribution with an unfairness less than 7.

**Constraints:**

`2 <= cookies.length <= 8`

`1 <= cookies[i] <= 10`

^{5}`2 <= k <= cookies.length`

**Related Topics**:

Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

**Similar Questions**:

- Split Array Largest Sum (Hard)
- Split Array with Equal Sum (Hard)
- Partition to K Equal Sum Subsets (Medium)
- Minimum XOR Sum of Two Arrays (Hard)
- The Number of Good Subsets (Hard)
- Minimum Number of Work Sessions to Finish the Tasks (Medium)
- Partition Array Into Two Arrays to Minimize Sum Difference (Hard)

## Solution 1. DP

Brute force is assigning each bag to different children. So there are `8^8 ~= 2e7`

ways and will get TLE.

The Brute force way has lots of duplicated computations. We can use DP to reduce such duplication.

Let `dp[k][m]`

be the min unfairness of bags represented by bitmask `m`

distributed to `k`

children.

If we assign bags represented by `m`

to a single child, the unfairness is `sum(m)`

, i.e. the sum of cookies in bags represented by `m`

.

```
dp[1][m] = sum(m)
```

For `dp[k][m]`

, we can try `m`

’s different subset `s`

as the bags assigned to the last child, so this child get `sum(s)`

. The rest of bags represented by `m-s`

are assigned to `k-1`

children.

```
dp[k][m] = min( max(dp[k-1][m-s], sum(s)) | s is a subset of m )
```

The answer is `dp[K][(1<<N)-1]`

.

```
// OJ: https://leetcode.com/problems/fair-distribution-of-cookies/
// Time: O(2^N * N + K * 3^N)
// Space: O(K * 2^N)
class Solution {
public:
int distributeCookies(vector<int>& A, int K) {
int N = A.size();
vector<vector<int>> dp(K + 1, vector<int>(1 << N, INT_MAX));
vector<int> sum(1 << N);
for (int m = 1; m < (1 << N); ++m) {
int s = 0;
for (int i = 0; i < N; ++i) {
if (m >> i & 1) s += A[i];
}
sum[m] = s;
dp[1][m] = s;
}
for (int k = 2; k <= K; ++k) {
for (int m = 1; m < (1 << N); ++m) {
for (int s = m; s; s = (s - 1) & m) {
dp[k][m] = min(dp[k][m], max(dp[k - 1][m - s], sum[s]));
}
}
}
return dp[K][(1 << N) - 1];
}
};
```

## Solution 2. DP with Space Optimization

Since `dp[k][m]`

only depends on `dp[k-1][m-s]`

, we can reduce the space for the `dp`

array from `K * 2^N`

to `2^N`

.

```
// OJ: https://leetcode.com/problems/fair-distribution-of-cookies/
// Time: O(2^N * N + K * 3^N)
// Space: O(2^N)
class Solution {
public:
int distributeCookies(vector<int>& A, int K) {
int N = A.size();
vector<int> dp(1 << N, INT_MAX), next(1 << N), sum(1 << N);
for (int m = 1; m < (1 << N); ++m) {
int s = 0;
for (int i = 0; i < N; ++i) {
if (m >> i & 1) s += A[i];
}
sum[m] = s;
dp[m] = s;
}
for (int k = 2; k <= K; ++k) {
fill(begin(next), end(next), INT_MAX);
for (int m = 1; m < (1 << N); ++m) {
for (int s = m; s; s = (s - 1) & m) {
next[m] = min(next[m], max(dp[m - s], sum[s]));
}
}
swap(dp, next);
}
return dp[(1 << N) - 1];
}
};
```