Fair Distribution of Cookies

You have k children and n bags of cookies. Distribute all bags among k children such that the maximum number of cookies any child gets is minimized. Return that minimum maximum.

Example 1

Input: cookies = [8,15,10,20,8], k = 2 → Output: 31

Example 2

Input: cookies = [6,1,3,2,2,4,1,2], k = 3 → Output: 7

Solution Approach

Use backtracking over all assignments. Try giving each cookie bag to each child. Prune branches where a child's current total already exceeds our best answer.

Maintain an array children[] of size k tracking each child's total.
At each bag index, try assigning it to each child.
After assigning, recurse to the next bag; then backtrack.
When all bags are distributed, update the global minimum with max(children[]).

Java

class Solution {
    int ans = Integer.MAX_VALUE;

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

    private void backtrack(int[] cookies, int[] children, int idx) {
        if (idx == cookies.length) {
            int max = 0;
            for (int c : children) max = Math.max(max, c);
            ans = Math.min(ans, max);
            return;
        }
        for (int i = 0; i < children.length; i++) {
            children[i] += cookies[idx];
            if (children[i] < ans)
                backtrack(cookies, children, idx + 1);
            children[i] -= cookies[idx];
            if (children[i] == 0) break; // symmetry pruning
        }
    }
}

Time Complexity: O(k^n) worst case with pruning
Space Complexity: O(k + n). Children array + stack