# Fair Distribution of Cookies
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fair-distribution-of-cookies)
Canonical: https://scaleengineer.com/dsa/problems/fair-distribution-of-cookies
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
You are given an integer array `cookies`, where `cookies[i]` denotes the number of cookies in the `ith` bag. You are also given an integer `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 = 2
**Output:** 31
**Explanation:** One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd 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 = 3
**Output:** 7
**Explanation:** One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd 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] <= 105`
* `2 <= k <= cookies.length`

# Approaches
## Brute-force Backtracking
This is a straightforward approach that explores every possible distribution of cookie bags to the `k` children. It uses a recursive function that, for each cookie bag, tries assigning it to every child and then moves to the next bag. When all bags are distributed, it calculates the unfairness and updates the minimum unfairness found so far.
**Time:** O(k^n), where `n` is the number of cookie bags and `k` is the number of children. For each of the `n` bags, there are `k` choices of which child to give it to, leading to `k^n` possible distributions in the recursion tree. · **Space:** O(n + k), where `n` is the number of cookie bags and `k` is the number of children. This is for the recursion stack depth (`O(n)`) and the `distribution` array (`O(k)`).
**Pros:** Simple to understand and implement.; Correctly explores the entire search space to guarantee the optimal solution.
**Cons:** Highly inefficient due to its exponential time complexity.; Explores many redundant and symmetric states, making it too slow for the given constraints without timing out on some platforms.
### Explanation
We define a recursive function, say `backtrack(cookieIndex, distribution)`, where `cookieIndex` is the index of the current cookie bag to be distributed, and `distribution` is an array of size `k` storing the current total cookies for each child.

The base case for the recursion is when `cookieIndex` reaches `cookies.length`. At this point, we have a complete distribution. We find the maximum value in the `distribution` array (the unfairness) and compare it with a global minimum, updating it if the current distribution is better.

In the recursive step, we iterate from `i = 0` to `k-1`. For each child `i`, we tentatively assign `cookies[cookieIndex]` to them (by adding to `distribution[i]`), make a recursive call for the next cookie (`cookieIndex + 1`), and then backtrack by undoing the assignment (subtracting `cookies[cookieIndex]` from `distribution[i]`).

The process starts with `backtrack(0, new int[k])`.

```java
class Solution {
    int minUnfairness = Integer.MAX_VALUE;

    public int distributeCookies(int[] cookies, int k) {
        backtrack(0, cookies, new int[k]);
        return minUnfairness;
    }

    private void backtrack(int cookieIndex, int[] cookies, int[] distribution) {
        if (cookieIndex == cookies.length) {
            int currentMax = 0;
            for (int sum : distribution) {
                currentMax = Math.max(currentMax, sum);
            }
            minUnfairness = Math.min(minUnfairness, currentMax);
            return;
        }

        for (int i = 0; i < distribution.length; i++) {
            distribution[i] += cookies[cookieIndex];
            backtrack(cookieIndex + 1, cookies, distribution);
            distribution[i] -= cookies[cookieIndex]; // Backtrack
        }
    }
}
```
### Algorithm
- 1. Initialize a global variable `minUnfairness` to a very large value (e.g., `Integer.MAX_VALUE`).
- 2. Create an integer array `distribution` of size `k`, initialized to all zeros, to keep track of the cookies assigned to each child.
- 3. Define a recursive function `backtrack(cookieIndex, distribution)`.
- 4. **Base Case:** If `cookieIndex` equals `cookies.length`, all bags have been distributed. Calculate the maximum value in the `distribution` array. This is the unfairness for the current distribution. Update `minUnfairness = min(minUnfairness, currentUnfairness)` and return.
- 5. **Recursive Step:** For the cookie bag at `cookieIndex`, iterate through each child `i` from `0` to `k-1`.
- 6. In the loop, add `cookies[cookieIndex]` to `distribution[i]` to assign the bag to child `i`.
- 7. Make a recursive call for the next cookie bag: `backtrack(cookieIndex + 1, distribution)`.
- 8. After the recursive call returns, subtract `cookies[cookieIndex]` from `distribution[i]`. This is the "backtracking" step, which undoes the choice to explore other possibilities.
- 9. To start the process, call `backtrack(0, new int[k])` from the main function.
- 10. After the initial call completes, `minUnfairness` will hold the minimum possible unfairness.

## Optimized Backtracking with Pruning
This approach significantly improves upon the brute-force method by adding several key optimizations to the backtracking algorithm. These optimizations reduce the search space by avoiding redundant calculations and cutting off unpromising paths early.
**Time:** The worst-case complexity is still exponential, but significantly faster in practice than brute-force. The number of states explored is related to partitioning `n` items into `k` groups (described by Stirling numbers of the second kind), which is much smaller than `k^n`. · **Space:** O(n + k) for the recursion depth (`O(n)`) and the `distribution` array (`O(k)`).
**Pros:** Much more efficient than the naive approach.; Pruning and symmetry breaking drastically reduce the search space, making it feasible for the given constraints.
**Cons:** The logic for optimizations, especially symmetry breaking, can be subtle to implement correctly.; The worst-case time complexity remains exponential, although it performs much better on average.
### Explanation
The core idea is still backtracking, but we add pruning and symmetry-breaking techniques.

- **1. Pruning:** If at any point, a child's current cookie sum `distribution[i]` plus the current cookie `cookies[cookieIndex]` is already greater than or equal to the best `minUnfairness` found so far, we can prune this entire branch of the recursion. This path cannot possibly lead to a better solution.
- **2. Sorting:** Sorting the `cookies` array in descending order makes the pruning more effective. By assigning larger cookies first, we are more likely to hit the `minUnfairness` bound early, allowing for more aggressive pruning.
- **3. Symmetry Breaking:** If we are assigning a cookie to a child who currently has zero cookies, it doesn't matter which empty-handed child we choose. They are all equivalent. To avoid exploring these symmetric states, we can enforce a rule: if we assign a cookie to an empty-handed child and that recursive path is fully explored, we don't need to try assigning the same cookie to other empty-handed children. This can be implemented by breaking the loop over children after backtracking from the first child with a sum of 0.

```java
class Solution {
    int minUnfairness = Integer.MAX_VALUE;

    public int distributeCookies(int[] cookies, int k) {
        // Sorting in descending order is a good heuristic for pruning
        Arrays.sort(cookies);
        reverse(cookies);
        backtrack(0, cookies, new int[k], k);
        return minUnfairness;
    }

    private void backtrack(int cookieIndex, int[] cookies, int[] distribution, int k) {
        if (cookieIndex == cookies.length) {
            int currentMax = 0;
            for (int sum : distribution) {
                currentMax = Math.max(currentMax, sum);
            }
            minUnfairness = Math.min(minUnfairness, currentMax);
            return;
        }

        for (int i = 0; i < k; i++) {
            // Pruning
            if (distribution[i] + cookies[cookieIndex] >= minUnfairness) {
                continue;
            }

            distribution[i] += cookies[cookieIndex];
            backtrack(cookieIndex + 1, cookies, distribution, k);
            distribution[i] -= cookies[cookieIndex]; // Backtrack

            // Symmetry Breaking
            if (distribution[i] == 0) {
                break;
            }
        }
    }
    
    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
}
```
### Algorithm
- 1. Initialize `minUnfairness` to a very large value.
- 2. Sort the `cookies` array in descending order. This is a heuristic that helps pruning to be more effective.
- 3. Define a recursive function `backtrack(cookieIndex, distribution)`.
- 4. **Base Case:** If `cookieIndex == cookies.length`, all bags are distributed. Calculate the maximum of the `distribution` array and update `minUnfairness`.
- 5. **Recursive Step:** For the current cookie `cookies[cookieIndex]`, loop through all children `i` from `0` to `k-1`.
- 6. **Pruning:** Before assigning the cookie, check if `distribution[i] + cookies[cookieIndex] >= minUnfairness`. If it is, this path cannot lead to a better solution, so `continue` to the next child.
- 7. Assign the cookie: `distribution[i] += cookies[cookieIndex]`.
- 8. Recurse: `backtrack(cookieIndex + 1, distribution)`.
- 9. Backtrack: `distribution[i] -= cookies[cookieIndex]`.
- 10. **Symmetry Breaking:** After backtracking, if `distribution[i]` is now `0`, it means we have fully explored the path of giving `cookies[cookieIndex]` to a previously empty-handed child. To avoid symmetric states, we can `break` the loop, as giving this cookie to any other empty-handed child is an equivalent scenario.
- 11. Start the process by calling `backtrack(0, new int[k])`.

## Binary Search on the Answer with Backtracking
This advanced approach transforms the problem. Instead of searching for the minimum unfairness value directly, we binary search for it. For any given value `x`, we can determine if it's *possible* to achieve an unfairness of at most `x`. This decision problem ("is it possible?") can be solved efficiently with a pruned backtracking search.
**Time:** O(T_backtrack * log(S)), where `S` is the sum of all cookies and `T_backtrack` is the time for the backtracking check. The `log(S)` factor comes from the binary search. While `T_backtrack` is exponential in the worst case, the tight bound `mid` makes it very fast in practice. · **Space:** O(n + k) for the recursion stack and the `distribution` array used within the `canDistribute` check.
**Pros:** Generally the most efficient approach for this class of problems.; The binary search framework provides a very tight bound for the backtracking search, leading to aggressive and effective pruning.
**Cons:** More complex to implement, as it combines two different algorithmic ideas (binary search and backtracking).; The backtracking check function still has an exponential worst-case time complexity.
### Explanation
The possible values for the minimum unfairness lie in a range. The lower bound is the largest single cookie bag, and the upper bound is the sum of all cookies. We can binary search within this range.

For each `mid` value in our binary search, we call a function `canDistribute(mid)`. This function returns `true` if there exists a distribution where no child gets more than `mid` cookies, and `false` otherwise.

- If `canDistribute(mid)` is `true`, it means `mid` is a possible unfairness, so we try for a smaller value by setting `high = mid - 1` and storing `mid` as a potential answer.
- If `canDistribute(mid)` is `false`, `mid` is too small, so we must allow a larger unfairness by setting `low = mid + 1`.

The `canDistribute` function itself is implemented using the same optimized backtracking logic as in the previous approach. The key difference is that the pruning condition is now `distribution[i] + cookies[cookieIndex] > mid`, and the function returns `true` as soon as a valid distribution is found, rather than searching for the best one.

```java
class Solution {
    public int distributeCookies(int[] cookies, int k) {
        int low = 0, high = 0;
        for (int c : cookies) {
            low = Math.max(low, c);
            high += c;
        }

        int ans = high;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canDistribute(cookies, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean canDistribute(int[] cookies, int k, int maxAllowed) {
        int[] distribution = new int[k];
        // Sorting helps the backtracking check to be more efficient
        Arrays.sort(cookies);
        reverse(cookies);
        return backtrackCheck(0, cookies, distribution, maxAllowed);
    }

    private boolean backtrackCheck(int cookieIndex, int[] cookies, int[] distribution, int maxAllowed) {
        if (cookieIndex == cookies.length) {
            return true;
        }

        for (int i = 0; i < distribution.length; i++) {
            if (distribution[i] + cookies[cookieIndex] > maxAllowed) {
                continue;
            }

            distribution[i] += cookies[cookieIndex];
            if (backtrackCheck(cookieIndex + 1, cookies, distribution, maxAllowed)) {
                return true;
            }
            distribution[i] -= cookies[cookieIndex]; // Backtrack

            if (distribution[i] == 0) {
                break;
            }
        }
        return false;
    }
    
    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
}
```
### Algorithm
- 1. Define a search range for the answer. Let `low` be the largest cookie value and `high` be the sum of all cookies.
- 2. Perform a binary search in the range `[low, high]`.
- 3. In each iteration, calculate `mid = low + (high - low) / 2`. `mid` is our candidate for the minimum unfairness.
- 4. Call a helper function `canDistribute(mid)` that returns `true` if a distribution with unfairness at most `mid` is possible, and `false` otherwise.
- 5. The `canDistribute(mid)` function uses a pruned backtracking search. It tries to distribute all cookies such that no child's sum exceeds `mid`. It should also use optimizations like sorting and symmetry breaking for efficiency.
- 6. If `canDistribute(mid)` returns `true`, it means `mid` is a possible answer. We try for an even better (smaller) one by setting `ans = mid` and `high = mid - 1`.
- 7. If `canDistribute(mid)` returns `false`, `mid` is too small to be a valid unfairness. We must allow a larger value, so we set `low = mid + 1`.
- 8. The loop continues until `low > high`, and the final `ans` is the minimum unfairness.

# Solutions
### Java

```java
class Solution { private int [] cookies ; private int [] cnt ; private int k ; private int n ; private int ans = 1 << 30 ; public int distributeCookies ( int [] cookies , int k ) { n = cookies . length ; cnt = new int [ k ]; // 升序排列 Arrays . sort ( cookies ); this . cookies = cookies ; this . k = k ; // 这里搜索顺序是 n-1, n-2,...0 dfs ( n - 1 ); return ans ; } private void dfs ( int i ) { if ( i < 0 ) { // ans = Arrays.stream(cnt).max().getAsInt(); ans = 0 ; for ( int v : cnt ) { ans = Math . max ( ans , v ); } return ; } for ( int j = 0 ; j < k ; ++ j ) { if ( cnt [ j ] + cookies [ i ] >= ans || ( j > 0 && cnt [ j ] == cnt [ j - 1 ])) { continue ; } cnt [ j ] += cookies [ i ]; dfs ( i - 1 ); cnt [ j ] -= cookies [ i ]; } } }
```

### CPP

```cpp
class Solution {
public:
  int distributeCookies(vector<int> &cookies, int k) {
    sort(cookies.rbegin(), cookies.rend());
    int cnt[k];
    memset(cnt, 0, sizeof cnt);
    int n = cookies.size();
    int ans = 1 << 30;
    function<void(int)> dfs = [&](int i) {
      if (i >= n) {
        ans = *max_element(cnt, cnt + k);
        return;
      }
      for (int j = 0; j < k; ++j) {
        if (cnt[j] + cookies[i] >= ans || (j && cnt[j] == cnt[j - 1])) {
          continue;
        }
        cnt[j] += cookies[i];
        dfs(i + 1);
        cnt[j] -= cookies[i];
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int: def dfs(i): if i >= len(cookies): nonlocal ans ans = max(cnt) return for j in range(k): if cnt[j] + cookies[i] >= ans or (j and cnt[j] == cnt[j - 1]): continue cnt[j] += cookies[i] dfs(i + 1) cnt[j] -= cookies[i] ans = inf cnt = [0] * k cookies . sort(reverse=True) dfs(0) return ans

```