Fair Distribution of Cookies
Last Updated: April 2, 2026
Understanding the Problem
We have some bags of cookies and some children. Every bag must be given to exactly one child (no splitting bags), and we want to minimize the maximum total any single child receives. In other words, we want the most "fair" distribution, where fairness is measured by how heavy the most-loaded child's pile is.
This is fundamentally an assignment problem. Each bag must go to one of k children, and we want the assignment that minimizes the maximum sum across all children. Think of it like partitioning the array into k groups to minimize the maximum group sum.
The key observation is that cookies.length is at most 8. That's a tiny search space. Each of the n bags can be assigned to any of the k children, giving us k^n total assignments. With k and n both at most 8, the worst case is 8^8 = about 16.7 million, which is manageable with backtracking and pruning.
Key Constraints:
2 <= cookies.length <= 8-> With at most 8 bags, exponential approaches like backtracking through all assignments (k^n) are perfectly feasible. Even 8^8 ~ 16.7 million is well within time limits.1 <= cookies[i] <= 10^5-> Cookie counts are positive, so every child who gets at least one bag will have a positive total. The maximum possible total for one child is 8 * 10^5 = 800,000.2 <= k <= cookies.length-> There are at least as many bags as children, so it's always possible to give each child at least one bag.
Approach 1: Brute Force Backtracking
Intuition
The most natural approach: for each bag of cookies, try assigning it to each of the k children. Once all bags are assigned, compute the maximum total across all children and track the minimum.
Since each of the n bags can go to any of k children, there are k^n total assignments. With n = 8 and k = 8 in the worst case, that's 8^8 = 16,777,216 assignments. That's a lot, but it's within the range of what a computer can handle in a couple of seconds.
We use a simple recursive approach: process bags one at a time, and for each bag, try giving it to each child. When we've assigned all bags, we record the unfairness (the max of all children's totals) if it's better than what we've seen so far.
Algorithm
- Create an array
childrenof size k, initialized to zeros, to track each child's current cookie total. - Recursively process bags from index 0 to n-1.
- For each bag, try assigning it to each of the k children by adding
cookies[i]to that child's total. - After assigning, recurse to the next bag. After returning, undo the assignment (backtrack).
- When all bags are assigned, compute the maximum value in
childrenand update the global minimum if it's lower. - Return the global minimum.
Example Walkthrough
Input:
We try every possible assignment of 5 bags to 2 children. For example, giving all bags to Child 0 yields max = 61. Giving [8,15,8] to Child 0 and [10,20] to Child 1 yields max(31, 30) = 31. Among all k^n = 32 assignments, the minimum unfairness is 31.
Code
- Time Complexity: O(k^n), where n is the number of cookie bags and k is the number of children. For each of the n bags, we try k assignments, giving k^n total branches in the recursion tree.
- Space Complexity: O(n + k). The recursion stack goes n levels deep, and we maintain a children array of size k.
The brute force tries every assignment, but many are redundant. If multiple children have the same total, assigning a bag to any of them is equivalent. What if we skipped redundant assignments and pruned hopeless branches early?
Approach 2: Backtracking with Pruning
Intuition
The brute force works but does a lot of unnecessary work. Two key observations let us prune the search tree dramatically:
- Upper bound pruning. If any child's current total already meets or exceeds our best known answer, there's no point continuing down this path. The unfairness can only get worse as we assign more bags.
- Symmetry breaking. If multiple children currently have the same total (especially zero), assigning the current bag to any one of them is equivalent. We only need to try one representative. This is a huge optimization because at the start of the recursion, all k children have zero cookies. Without this pruning, we'd explore k identical branches at the first level.
There's a third useful optimization: sorting the cookies array in descending order. By assigning the largest bags first, we reach higher totals sooner, which triggers the upper bound pruning earlier and cuts off more branches.
The pruning optimizations don't change the correctness of the algorithm. They only skip branches that are guaranteed to not improve the result. Upper bound pruning is safe because adding more cookies to a child can only increase their total, never decrease it. Symmetry breaking is safe because if two children have the same total, assigning the current bag to either one produces structurally identical subproblems.
Algorithm
- Sort
cookiesin descending order (largest bags first for earlier pruning). - Create an array
childrenof size k, initialized to zeros. - Maintain a global
resultinitialized to the total sum of all cookies. - Recursively assign bags starting from index 0.
- At each step, for each child, assign the current bag only if adding this bag doesn't make the child's total >= current best result (upper bound pruning), and this child is the first one with this particular total value (symmetry breaking).
- After assigning, recurse to the next bag, then backtrack.
- When all bags are assigned, update the result with the maximum child total.
Example Walkthrough
Code
- Time Complexity: O(k^n) in the worst case, but with pruning the practical runtime is much lower. The symmetry breaking alone reduces the first level from k branches to 1.
- Space Complexity: O(n + k). The recursion stack is n levels deep, and we maintain a children array of size k. The seen set at each level has at most k entries.
The backtracking with pruning is fast enough for these constraints, but there's a fundamentally different approach using bitmask DP that gives a cleaner complexity guarantee.
Approach 3: Bitmask Dynamic Programming
Intuition
Instead of assigning bags to children one at a time, we represent which bags have been assigned using a bitmask. If there are n bags, a bitmask of n bits can represent any subset. Bit i being set means bag i has been assigned.
First, precompute the sum of cookies for every possible subset (all 2^n subsets). Then define dp[j][mask] as the minimum unfairness when distributing the bags in mask among the first j children. For each child, we try every possible subset of the remaining bags to give them, and take the minimum over all valid partitions.
This approach has a clean O(k * 3^n) complexity because for each mask, iterating over all subsets of that mask across all masks totals 3^n (by the inclusion-exclusion principle: each element is in the outer mask, in the inner subset, or in neither).
The DP formulation correctly considers every way to partition the bags among k children. By iterating over subsets of subsets, we cover all possible groupings. The max in the transition ensures we track the child with the heaviest load (the unfairness), and the min over all choices ensures we pick the partition that minimizes that maximum.
Algorithm
- Precompute
subsetSum[mask]for all 2^n masks, where each mask represents a subset of bags. - Initialize
dp[0][0] = 0(zero children assigned, no bags distributed, unfairness is 0) and everything else to infinity. - For each child j from 1 to k, for each mask, enumerate all subsets
subofmaskand computedp[j][mask] = min(dp[j][mask], max(dp[j-1][mask ^ sub], subsetSum[sub])). - Return
dp[k][(1 << n) - 1](all k children assigned, all bags distributed).
Example Walkthrough
Code
- Time Complexity: O(k 3^n), where n is the number of bags. The subset enumeration across all masks totals 3^n per child. With n = 8, that's k 6561, which is very fast.
- Space Complexity: O(k 2^n) for the DP table. With n = 8 and k = 8, that's 8 256 = 2048 integers.