Code Implementation

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        n = len(cookies)
        ans = float('inf')
        distribution = [0] * k

        def backtrack(i):
            nonlocal ans
            if i == n:
                ans = min(ans, max(distribution))
                return
            for j in range(k):
                distribution[j] += cookies[i]
                # Prune: do not continue if current max already exceeds best answer
                if max(distribution) < ans:
                    backtrack(i + 1)
                distribution[j] -= cookies[i]
                # Optimization: If this bucket is empty, don't try the same for other empty buckets
                if distribution[j] == 0:
                    break

        backtrack(0)
        return ans
      

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n = cookies.size();
        int ans = INT_MAX;
        vector<int> distribution(k, 0);

        function<void(int)> backtrack = [&](int i) {
            if (i == n) {
                ans = min(ans, *max_element(distribution.begin(), distribution.end()));
                return;
            }
            for (int j = 0; j < k; ++j) {
                distribution[j] += cookies[i];
                if (*max_element(distribution.begin(), distribution.end()) < ans)
                    backtrack(i + 1);
                distribution[j] -= cookies[i];
                if (distribution[j] == 0) break;
            }
        };

        backtrack(0);
        return ans;
    }
};
      

class Solution {
    int ans = Integer.MAX_VALUE;

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

    private void backtrack(int[] cookies, int i, int[] distribution, int k) {
        if (i == cookies.length) {
            int max = 0;
            for (int x : distribution) max = Math.max(max, x);
            ans = Math.min(ans, max);
            return;
        }
        for (int j = 0; j < k; ++j) {
            distribution[j] += cookies[i];
            if (max(distribution) < ans)
                backtrack(cookies, i + 1, distribution, k);
            distribution[j] -= cookies[i];
            if (distribution[j] == 0) break;
        }
    }

    private int max(int[] arr) {
        int mx = 0;
        for (int x : arr) mx = Math.max(mx, x);
        return mx;
    }
}
      

var distributeCookies = function(cookies, k) {
    let ans = Infinity;
    let distribution = new Array(k).fill(0);

    function backtrack(i) {
        if (i === cookies.length) {
            ans = Math.min(ans, Math.max(...distribution));
            return;
        }
        for (let j = 0; j < k; ++j) {
            distribution[j] += cookies[i];
            if (Math.max(...distribution) < ans)
                backtrack(i + 1);
            distribution[j] -= cookies[i];
            if (distribution[j] === 0) break;
        }
    }

    backtrack(0);
    return ans;
};
      

Problem Description

You are given an array cookies where cookies[i] is the number of cookies in the i-th bag. There are k children, and you want to distribute all the bags to these children. Each bag must go to exactly one child, and each child can receive any number of bags (including none).

The unfairness of a distribution is the maximum total number of cookies received by any single child.

Your task is to distribute the bags such that the unfairness is minimized. That is, return the minimum possible value of unfairness over all valid distributions.

• Each bag must be given to exactly one child.
• No bag can be split or reused.
• There is always at least one valid distribution.

Constraints:

• 1 <= cookies.length <= 8
• 1 <= cookies[i] <= 10^5
• 1 <= k <= cookies.length

Thought Process

At first glance, this problem seems to require trying every possible way to distribute the bags among the children, as we want to minimize the maximum sum any child gets. Since each bag can go to any child, there are k^n possible assignments (where n is the number of bags), which is large but manageable for small n.

The brute-force approach would be to generate all possible ways to assign bags to children, calculate the maximum sum for each assignment, and return the smallest maximum sum found.

However, this can be optimized by:

• Using backtracking to avoid generating all assignments explicitly.
• Pruning branches that are already worse than the current best solution.
• Stopping early when a distribution is known to be suboptimal.

Solution Approach

We use a backtracking algorithm to assign each bag to a child, keeping track of how many cookies each child has. At each step, we try to assign the current bag to every child, and recursively continue to the next bag.

• We keep an array distribution of length k, where distribution[j] is the total cookies assigned to child j so far.
• At each recursive call (for bag i), we try each child j:
  • Add cookies[i] to distribution[j].
  • Recursively assign the next bag.
  • Backtrack by removing cookies[i] from distribution[j].
• If all bags are assigned, we compute the maximum value in distribution (the current unfairness) and update our answer if it is better.
• We prune (stop recursion early) if the current maximum in distribution is already greater than or equal to our best answer so far.
• For further optimization, whenever we try to assign a bag to an empty child, we can skip assigning the same bag to other empty children in the same state (because distributions are symmetric).

This approach efficiently explores the search space and avoids redundant work.

Example Walkthrough

Suppose cookies = [8, 15, 10, 20, 8] and k = 2.

1. We start with both children having 0 cookies: [0, 0].
2. Assign the first bag (8) to child 0: [8, 0], then try all ways to assign the rest.
3. Assign the second bag (15) to child 0: [23, 0], and continue.
4. Continue assigning each bag to each child, recursively, updating the distribution array at each step.
5. At the leaf nodes (when all bags are assigned), calculate max(distribution) and update the answer if it is smaller.
6. For example, one possible assignment is: child 0 gets [8, 15, 8] = 31, child 1 gets [10, 20] = 30, so unfairness is 31. Another assignment could yield a better unfairness (e.g., 29).
7. Throughout, whenever a partial assignment already exceeds the current best unfairness, we prune that branch.

By the end, we find that the minimal unfairness for this input is 31.

Time and Space Complexity

Brute-force: There are k^n possible assignments (each of n bags can go to any of k children), so the time complexity is O(k^n). This is feasible only for small n (as in this problem).

Optimized (Backtracking with Pruning): In practice, pruning dramatically reduces the number of recursive calls, especially when k is small or the cookie sizes vary greatly. However, in the worst case, the time complexity remains O(k^n), but the constant factor is much improved.

Space Complexity: The main space usage is the recursion stack and the distribution array of size k, so the space complexity is O(n + k).

Summary

The Fair Distribution of Cookies problem asks us to minimize the maximum cookies any child receives when distributing bags. By using backtracking with effective pruning and symmetry optimizations, we can efficiently solve the problem for small input sizes. The key insights are to try all assignments recursively, prune when a partial solution is already worse than the best found, and avoid redundant symmetric states. This approach is both elegant and practical for the given constraints.