Fair Distribution of Cookies - Video Solutions

Problem Overview: You are given an array where each element represents a bag of cookies and an integer k representing children. Each bag must go to exactly one child. The goal is to minimize unfairness, defined as the maximum number of cookies received by any child.

Approach 1: Backtracking with Pruning (Time: O(k^n), Space: O(n))

This approach tries every possible way to distribute cookie bags among k children using backtracking. Maintain an array where dist[i] tracks the total cookies assigned to the i-th child. For each bag, iterate through children and assign the bag recursively. After assigning all bags, compute the maximum value in dist and track the minimum possible unfairness.

Pruning significantly reduces the search space. If the current distribution already exceeds the best unfairness found so far, stop exploring that branch. Another common optimization skips assigning a bag to multiple children with the same current cookie count to avoid duplicate states. This approach is practical because the constraint on the number of bags is small.

Approach 2: Dynamic Programming with Bitmasking (Time: O(k * 3^n), Space: O(k * 2^n))

This approach models the problem using dynamic programming combined with bitmasking. Each bitmask represents a subset of cookie bags. First precompute the total cookies for every subset mask using bit operations. Then define dp[i][mask] as the minimum unfairness when distributing the bags represented by mask among i children.

For each state, iterate through all submasks of mask. Treat the submask as the set of bags assigned to the current child and combine it with the optimal distribution of the remaining bags. The unfairness becomes max(dp[i-1][mask ^ submask], subsetSum[submask]). Minimizing this value across all submasks gives the optimal distribution.

This method systematically explores subsets rather than permutations, making it easier to reason about overlapping subproblems. It performs well when the number of bags is small (typically ≤ 8), which keeps the bitmask state space manageable.

Recommended for interviews: The backtracking solution is usually expected. It demonstrates recursion, pruning, and state management. Interviewers want to see how you reduce exponential search with pruning. The bitmask dynamic programming approach is more advanced and shows deeper understanding of subset DP, which can stand out in system-level or algorithm-heavy interviews.