Fair Distribution of Cookies

MediumBacktracking · Bitmask DP🧩 Bitmask DP LeetCode #2305 ↗Updated Oct 30, 2026

Problem

cookies[i] is the number of cookies in bag i. Hand every bag, unopened, to one of k children. The unfairness of a split is the largest total any child receives; return the minimum possible unfairness.

Input[8,15,10,20,8], k = 2Output31 (8+15+8 | 10+20)

Input[6,1,3,2,2,4,1,2], k = 3Output7

2 ≤ n ≤ 8 · 1 ≤ cookies[i] ≤ 10⁵ · 2 ≤ k ≤ n

Try it yourself

Java

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

n ≤ 8 means the search space is tiny: either backtrack with strong pruning, or treat each child's share as a subset (bitmask) and do DP over “which bags are already handed out”.

PatternBitmask DP

Instinct n is tiny (about 20 or less) and you must use, visit or assign every item - make the set of used items a bitmask and DP over all 2^n subsets.

Memory hack Small n, big choice - let the bits keep score: each item is a light switch and the mask is the whole switch panel.

Open the Bitmask DP guide →

Approaches

Brute ForceTry Every Assignment

Time O(kⁿ)Space O(n + k)

Give bag i to each child in turn and recurse, carrying the running maximum. At the end, the running max is that split's unfairness; keep the smallest. The recursion tree has kⁿ leaves.

Java

private int best = Integer.MAX_VALUE;

public int distributeCookies(int[] cookies, int k) {
    dfs(cookies, new int[k], 0, 0);
    return best;
}
private void dfs(int[] cookies, int[] bins, int i, int curMax) {
    if (i == cookies.length) {
        best = Math.min(best, curMax);
        return;
    }
    for (int c = 0; c < bins.length; c++) {
        bins[c] += cookies[i];
        dfs(cookies, bins, i + 1, Math.max(curMax, bins[c]));
        bins[c] -= cookies[i];
    }
}

Simple and correct, but explores symmetric and hopeless branches.

BetterBacktracking + Pruning + Symmetry

Time O(kⁿ) worstSpace O(n + k)

Three cuts: hand out big bags first (bad branches fail early), skip a child if their total would reach best, and try only the first empty child — empty children are interchangeable, so the others repeat the same split.

Java

private int best = Integer.MAX_VALUE;

public int distributeCookies(int[] cookies, int k) {
    int[] c = cookies.clone();
    Arrays.sort(c); // assign from the largest bag down
    dfs(c, new int[k], c.length - 1, 0);
    return best;
}
private void dfs(int[] c, int[] bins, int i, int curMax) {
    if (i < 0) {
        best = curMax; // pruning guarantees curMax < best
        return;
    }
    for (int j = 0; j < bins.length; j++) {
        if (bins[j] + c[i] < best) {
            bins[j] += c[i];
            dfs(c, bins, i - 1, Math.max(curMax, bins[j]));
            bins[j] -= c[i];
        }
        if (bins[j] == 0) break; // other empty children are symmetric
    }
}

Same worst-case bound, but typically orders of magnitude fewer nodes.

OptimalBitmask DP over Subsets

Time O(k·3ⁿ)Space O(2ⁿ)

Precompute sum[mask]. Let dp[mask] = best unfairness giving exactly the bags in mask to the children so far. Adding one child who takes submask sub: max(sum[sub], dp[mask ^ sub]). Enumerating all submasks of all masks costs 3ⁿ per child.

Java

public int distributeCookies(int[] cookies, int k) {
    int n = cookies.length, 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 & (mask - 1)] + cookies[low];
    }
    int[] dp = sum.clone(); // one child takes everything in mask
    for (int child = 2; child <= k; child++) {
        int[] next = new int[1 << n];
        for (int mask = 0; mask <= full; mask++) {
            int best = dp[mask]; // new child gets nothing
            for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
                best = Math.min(best, Math.max(sum[sub], dp[mask ^ sub]));
            }
            next[mask] = best;
        }
        dp = next;
    }
    return dp[full];
}

Guaranteed polynomial in k: 8·3⁸ ≈ 52K steps vs 8⁸ ≈ 16.7M.

Pro tip

sub = (sub - 1) & mask walks every submask of mask in decreasing order — memorise this idiom.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Assignment	`O(kⁿ)`	`O(n + k)`
Better	Backtracking + Pruning + Symmetry	`O(kⁿ) worst`	`O(n + k)`
Optimal	Bitmask DP over Subsets	`O(k·3ⁿ)`	`O(2ⁿ)`

Common pitfalls

Greedy “give the bag to the poorest child” is not optimal (e.g. [3,3,2,2,2], k=2).
Breaking on an empty child before trying it — must try the first empty one once.
Recomputing the max over all k children at every leaf — carry curMax instead.

Interview tips

Read the constraints aloud: n ≤ 8 invites exponential search.
Explain the symmetry-breaking rule; it is the biggest practical speed-up.
Offer the bitmask DP for a guaranteed bound independent of kⁿ.

Pattern

Partition into k groups minimising the max → backtracking with pruning, or subset/bitmask DP when n ≤ ~16.

My notes saved in this browser