Free lesson · DSA Mastery - Interview Prep, End to End
Fair Distribution of Cookies
Fair Distribution of Cookies
Fair Distribution of Cookies is another subset-only Bitmask DP: distribute n cookies among k children to minimize the maximum total per child. The DP defines dp[mask][k] = minimum (over assignments) of "max child-total" when distributing the cookies in mask among k children. Transition: pick a non-empty subset s of mask to give to the k-th child; recurse on dp[mask \ s][k-1]. It introduces iterating over subsets of a subset - the s = (s-1) & mask enumeration trick - and demonstrates handling partition problems where the partition count K is a fixed parameter. We present the bitmask + K DP with subset-of-subset enumeration (canonical).
The insight: distributing cookies fairly is a K-partition problem - split the cookies into K groups, minimize the maximum group total. The DP enumerates "what subset does the last child get?" - try every non-empty subset s of the current cookies; the last child's total is sum(s); the remaining children handle mask \ s with k-1 children. The answer is max(sum(s), dp[mask \ s][k-1]). Minimize over all such s. The bitmask state captures "which cookies remain to distribute."
The Problem
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the i-th bag. You are also given an integer k that denotes the number of children to distribute the bags 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] (= 31) and [10,20] (= 30); max = 31.
Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal: [6,1] (=7), [3,2,2] (=7), [4,1,2] (=7); max = 7.
Constraints:
2 <= cookies.length <= 8;1 <= cookies[i] <= 10^5;2 <= k <= cookies.length.
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Bitmask DP with subset-of-subset enumeration | O(k · 3^n) | O(k · 2^n) | Canonical |
Precompute sum[mask] = total of cookies in subset mask. dp[mask][j] = minimum unfairness when distributing the cookies in mask to j children. Base: dp[mask][1] = sum[mask] (one child takes everything). Transition: for each non-empty subset s of mask, dp[mask][j] = min(dp[mask][j], max(sum[s], dp[mask ^ s][j-1])). Answer: dp[FULL][k].
Total complexity O(k · 3^n) comes from iterating over (mask, sub-mask) pairs: the sum of 2^popcount(mask) over all masks equals 3^n.
Approach: Bitmask DP with Subset-of-Subset Enumeration - Canonical
The Idea
Enumerate all ways to partition the cookies into K groups, but smartly: fix the last group as some non-empty subset of remaining cookies, then recurse. Memoization over the (remaining-cookies, remaining-children) state avoids redundant recomputation.
Logic Flowchart
graph TD
A["precompute sum[mask] for all mask"] --> B["dp[mask][1] = sum[mask] (single child)"]
B --> C["for j from 2 to k:"]
C --> D["for each mask:"]
D --> E["dp[mask][j] = INF"]
E --> F["for each non-empty subset s of mask: (s = mask, s = (s-1) & mask, ... until s = 0)"]
F --> G["candidate = max(sum[s], dp[mask ^ s][j-1])"]
G --> H["dp[mask][j] = min(dp[mask][j], candidate)"]
H --> F
F --> D
D --> C
C --> I["return dp[FULL][k]"]
style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows Fair Distribution of Cookies: precompute subset sums, fill the dp by increasing number of children, and at each (mask, j) enumerate every non-empty subset s of mask as the last child's portion.
Code
public static int distributeCookies(int[] cookies, int k) {
int n = cookies.length;
int FULL = (1 << n) - 1;
int[] sum = new int[1 << n];
for (int mask = 1; mask <= FULL; mask++) {
int low = Integer.numberOfTrailingZeros(mask);
sum[mask] = sum[mask ^ (1 << low)] + cookies[low];
}
int[][] dp = new int[1 << n][k + 1];
for (int mask = 0; mask <= FULL; mask++) dp[mask][1] = sum[mask];
for (int j = 2; j <= k; j++) {
for (int mask = 0; mask <= FULL; mask++) {
dp[mask][j] = Integer.MAX_VALUE;
for (int s = mask; s > 0; s = (s - 1) & mask) {
int cand = Math.max(sum[s], dp[mask ^ s][j - 1]);
if (cand < dp[mask][j]) dp[mask][j] = cand;
}
}
}
return dp[FULL][k];
}
// Usage:
// distributeCookies([8,15,10,20,8], 2) -> 31
// distributeCookies([6,1,3,2,2,4,1,2], 3) -> 7
This Java code distributes cookies fairly via bitmask DP, with subset-sum precomputation and subset-of-subset enumeration to find the optimal last-child portion.
Step-by-Step Walkthrough
Tracing distributeCookies([8,15,10,20,8], 2):
graph LR
F0["sum precomputed for all 32 masks"]
F1["dp[mask][1] = sum[mask] for all mask"]
F2["dp[FULL][2]: enumerate non-empty subsets s of 0b11111; for each compute max(sum[s], sum[FULL ^ s]); min over all such pairs"]
F3["best split: s = 0b00111 (cookies 0,1,2 = 8+15+10=33) and 0b11000 (20+8=28), max=33 - not optimal; best is s=0b10101 (8+10+8=26) and 0b01010 (15+20=35), max=35; another: s=0b10011 (8+15+8=31) and 0b01100 (10+20=30), max=31 - answer"]
F0 --> F1 --> F2 --> F3
style F0 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough computes the fairest split into two children: enumerate every non-empty subset of cookies as one child's portion, pair with the complement, take the min of the max.
Result: 31.
Complexity
Time: O(k · 3^n). For n = 8: k · 6561 ≈ 60,000 - trivial. Space: O(k · 2^n).
Complexity Comparison
| Approach | Time | Space | Key Idea |
|---|---|---|---|
| Bitmask DP + subset-of-subset | O(k · 3^n) | O(k · 2^n) | per (mask, j), enumerate non-empty subsets s of mask as last child's portion |
The bitmask DP is the canonical solution. The 3^n complexity from subset-of-subset enumeration is the standard cost for "split a subset into two non-empty parts" problems.
Variations & Follow-ups
Why is the complexity 3^n, not 2^n · 2^n?
A naive analysis of "for each mask, enumerate each subset s of mask" gives 2^n · 2^n = 4^n - wrong. The correct count uses the combinatorial identity: the sum of 2^popcount(mask) over all masks of size n equals 3^n. Intuitively, each of n elements is in one of three states: (a) not in mask, (b) in mask but not in s, (c) in s. Three choices per element, n elements → 3^n total. The general lesson: iterating over (mask, sub-mask of mask) pairs is 3^n, not 4^n. This is one of the most important complexity facts for Bitmask DP. For n = 14: 3^14 ≈ 5 × 10⁶ - comfortable. For n = 16: 3^16 ≈ 4 × 10⁷ - borderline. For n > 18: typically too slow.
How does the s = (s-1) & mask subset enumeration work?
To enumerate all non-empty subsets of mask:
- Start with
s = mask. - At each step, set
s = (s - 1) & mask. - Stop when
s = 0.
The trick: subtracting 1 from s "flips" the lowest set bit and sets all lower bits; ANDing with mask restricts to bits actually in mask. Iterating produces all non-empty subsets of mask in decreasing order. (To include the empty subset, also process s = 0 after the loop, or restructure the loop.) The general lesson: the (s-1) & mask trick is the canonical subset-of-mask enumeration. Memorize this idiom - it appears in Bitmask DPs for partition, assignment, and grouping problems.
Why does the DP iterate by K (number of children) outermost?
The recurrence reads dp[mask ^ s][j-1] - a smaller j. So j must be filled in increasing order, with all j-1 values available before processing j. The order within j (over mask) doesn't matter for correctness because each (mask, j) cell reads only (mask', j-1) cells. The general lesson: Bitmask DPs with a secondary dimension (like K) need outer-loop ordering by that dimension. Inner-loop ordering over masks is free.
How does this compare to greedy approaches?
A greedy: sort cookies descending; assign each cookie to the currently-least-loaded child. This is the longest processing time first heuristic, achieving 4/3 approximation for makespan minimization on identical machines (Graham's bound). For exact answers with small n, DP wins; for large n, greedy is the practical choice. The general lesson: exact DPs solve the small-n version of NP-hard problems; greedy/approximation algorithms cover the large-n regime.
What about edge cases?
- K = 1: All cookies to one child; answer = total.
- K = N (each child gets ≥ 1 bag): Answer = max(cookies[]) (each child gets one bag, the max is the largest bag).
- All cookies equal: Equal distribution if n divisible by k.
- n = 8, k = 8: Each child gets exactly one bag.
Common Interview Pitfalls
- Enumerating all subsets (including empty) inadvertently. The empty subset would mean "give nothing to this child" - fine semantically if the problem allows empty assignments, but messes up the recurrence if not. Use
s > 0to skip empty. - Not precomputing sum[mask]. Computing it on the fly inside the loop costs O(n) per mask - turns the algorithm 3^n into 3^n · n, much slower.
- Off-by-one in K.
dp[FULL][k](notk-1ork+1) is the answer. - Confusing fairness objective. We minimize the maximum child's total -
max(sum[s], dp[...])notminorsum.
Why This Topic Matters
Fair Distribution of Cookies introduces subset-of-subset enumeration via the s = (s-1) & mask trick, with total complexity O(3^n). The state dp[mask][j] combines a bitmask (which cookies remain) with a secondary dimension (how many children remain). The objective (minimize the max child's total) is a makespan minimization - the central problem in scheduling theory. The same DP framework applies to a wide class of K-partition problems.
The next topic, Campus Bikes II, is an assignment Bitmask DP: given workers and bikes on a grid, assign each worker a unique bike to minimize total Manhattan distance. The DP defines dp[mask] = minimum total distance when the bikes in mask have been assigned (one worker each, in some fixed order). Transition: assign the next worker to any unused bike. It teaches the assignment problem via Bitmask DP - workers iterate by their fixed order, bikes by mask - and demonstrates that Bitmask DP solves the Hungarian-algorithm problem for small N in O(n · 2^n) time.