AlgoMaster Logo

Fair Distribution of Cookies

mediumFrequency9 min readUpdated June 23, 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 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. Equivalently, partition the array into k groups so the heaviest group sum is as small as possible.

What makes the problem tractable is the size limit: cookies.length is at most 8. Each of the n bags can be assigned to any of the k children, giving k^n total assignments. With k and n both at most 8, the worst case is 8^8 = about 16.7 million, which backtracking with pruning handles comfortably.

Key Constraints:

  • 2 <= cookies.length <= 8 -> With at most 8 bags, an exponential search through all k^n assignments runs in time. The worst case, 8^8 ~ 16.7 million, fits within typical limits, and pruning cuts it far below that.
  • 1 <= cookies[i] <= 10^5 -> Every cookie count is positive, so adding a bag to a child strictly raises its total. The maximum total one child can reach is 8 * 10^5 = 800,000, which fits in a 32-bit integer.
  • 2 <= k <= cookies.length -> There are at least as many bags as children, so a valid distribution always exists.

Approach 1: Brute Force Backtracking

Intuition

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 keep the smallest such maximum seen across all assignments.

Each of the n bags can go to any of k children, so there are k^n total assignments. With n = 8 and k = 8 in the worst case, that is 8^8 = 16,777,216 assignments, which runs in a couple of seconds.

The recursion processes bags one at a time. For each bag, it tries giving it to each child, recurses to the next bag, then undoes the choice. When all bags are assigned, it records the unfairness (the maximum of the children's totals) and updates the running best.

Algorithm

  1. Create an array children of size k, initialized to zeros, to track each child's current cookie total.
  2. Recursively process bags from index 0 to n-1.
  3. For each bag, try assigning it to each of the k children by adding cookies[i] to that child's total.
  4. After assigning, recurse to the next bag. After returning, undo the assignment (backtrack).
  5. When all bags are assigned, compute the maximum value in children and update the global minimum if it's lower.
  6. Return the global minimum.

Example Walkthrough

To keep every branch visible, trace a smaller input: cookies = [8, 15, 10], k = 2. There are k^n = 2^3 = 8 assignments. Each bag goes to either Child 0 or Child 1, and the assignment is written as a triple (one child index per bag).

Scroll

Assignment

Child 0

Child 1

max

best so far

(0, 0, 0)

8+15+10 = 33

0

33

33

(0, 0, 1)

8+15 = 23

10

23

23

(0, 1, 0)

8+10 = 18

15

18

18

(0, 1, 1)

8

15+10 = 25

25

18

(1, 0, 0)

15+10 = 25

8

25

18

(1, 0, 1)

15

8+10 = 18

18

18

(1, 1, 0)

10

8+15 = 23

23

18

(1, 1, 1)

0

8+15+10 = 33

33

18

The recursion visits these eight leaves in order. Each leaf computes the heavier child's total and lowers best when it improves. The first leaf sets best = 33, the second lowers it to 23, the third to 18, and no later leaf beats 18. The minimum unfairness is 18, achieved by putting bags {8, 10} with one child and {15} with the other.

Several leaves are mirror images of each other, for example (0, 0, 1) and (1, 1, 0) both produce totals 23 and 10. The brute force evaluates both. Removing that wasted work is what the next approach addresses.

Code

The brute force evaluates every assignment, including the many that are equivalent or already worse than a solution we have found. The next approach keeps the same recursion but skips both kinds of branch.

Approach 2: Backtracking with Pruning

Intuition

The brute force does redundant work. Two prunings shrink the search tree:

  1. Upper bound pruning. If adding the current bag would push a child's total to or past the best answer found so far, stop. Every remaining bag is positive, so that child's total can only grow, and this branch cannot improve the result.
  1. Symmetry breaking. If two children currently hold the same total, assigning the current bag to either one leads to structurally identical subproblems. Try only one of them. This matters most at the root, where all k children start at 0: without it, the first bag would spawn k identical subtrees.

A third refinement is sorting cookies in descending order. Assigning the largest bags first drives child totals up sooner, which makes the upper bound pruning fire earlier and cut off more branches.

Algorithm

  1. Sort cookies in descending order (largest bags first for earlier pruning).
  2. Create an array children of size k, initialized to zeros.
  3. Maintain a global result initialized to the total sum of all cookies.
  4. Recursively assign bags starting from index 0.
  5. 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).
  6. After assigning, recurse to the next bag, then backtrack.
  7. When all bags are assigned, update the result with the maximum child total.

Example Walkthrough

1Start: sorted cookies = [20,15,10,8,8], children = [0,0], result = 61
0
20
bag
1
15
2
10
3
8
4
8
1/9
1children = [0, 0], result = 61
0
0
C0
1
0
C1
1/9

Code

The backtracking runs fast enough here, but its worst-case time is still exponential and hard to bound tightly. A bitmask DP gives a fixed worst-case complexity that does not depend on lucky pruning.

Approach 3: Bitmask Dynamic Programming

Intuition

Instead of assigning bags to children one at a time, represent the set of assigned bags as a bitmask. With n bags, an n-bit mask describes any subset, where bit i set means bag i has been assigned.

Precompute the sum of cookies for every subset (all 2^n of them). Then define dp[j][mask] as the minimum unfairness when distributing exactly the bags in mask among the first j children. To extend from j-1 to j children, give child j some subset sub of mask and leave the rest mask ^ sub for the earlier children. The unfairness of that choice is the larger of child j's sum and the best unfairness achievable for the rest, and we minimize over all subsets sub.

The complexity is O(k * 3^n). For a fixed child, iterating over every subset of every mask costs 3^n total, because each bag is either outside mask, inside sub, or inside mask ^ sub, giving three independent choices per bag.

Algorithm

  1. Precompute subsetSum[mask] for all 2^n masks, where each mask represents a subset of bags.
  2. Initialize dp[0][0] = 0 (zero children assigned, no bags distributed, unfairness is 0) and everything else to infinity.
  3. For each child j from 1 to k, for each mask, enumerate all subsets sub of mask and compute dp[j][mask] = min(dp[j][mask], max(dp[j-1][mask ^ sub], subsetSum[sub])).
  4. Return dp[k][(1 << n) - 1] (all k children assigned, all bags distributed).

Example Walkthrough

Trace cookies = [8, 15, 10], k = 2. Bit 0 is bag 8, bit 1 is bag 15, bit 2 is bag 10, so mask 101 (binary) is the subset {8, 10} with sum 18 and mask 111 is all three bags with sum 33. The animation precomputes subsetSum, fills dp for one child, then combines two children over the full mask 111 to reach the answer 18.

1Precomputed subsetSum for all 2^3=8 masks. Index = bitmask of bags.
0
0
000:{}
1
8
001:{8}
2
15
010:{15}
3
23
011:{8,15}
4
10
5
18
6
25
7
33
1/6

Code