DSA problem
Fair Distribution of Cookies
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 all the bags of cookies 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.
Since each bag is indivisible, every bag of cookies is assigned wholesale to exactly one child. The natural way to encode the assignment for n bags is a bitmask of which bags have already been handed out. We pursue the children in order: child 0 receives some subset of bags, then child 1 receives some subset of the remaining bags, and so on. The unfairness is the max over children of the total received.
Because the children are interchangeable, we only need to enumerate subset assignments greedily in order. The classic bitmask DP defines dp[k][mask] = the minimum unfairness achievable when the first k children have collectively been handed exactly the bags in mask. Two different orders of giving the same subset to child 0 are equivalent — only the subset matters.
The optimal solution precomputes sum[mask] (the total cookies across the bags in mask) so each transition is O(1) per submask. The transition iterates over every non-empty submask sub of mask using the classic enumeration for (sub = mask; sub > 0; sub = (sub - 1) & mask), assigns sub to child k - 1, and minimises max(dp[k - 1][mask ^ sub], sum[sub]). The total work over all (mask, submask) pairs is 3^n (each bit is independently "in mask only", "in mask and sub", or "in neither"), multiplied by k children: O(k * 3^n) time and O(k * 2^n) space.
Examples
cookies = [8,15,10,20,8], k = 231cookies = [6,1,3,2,2,4,1,2], k = 37cookies = [1,1], k = 21Constraints
- 2 <= cookies.length <= 8
- 1 <= cookies[i] <= 10^5
- 2 <= k <= cookies.length
- Each bag must be given to exactly one child.
- You may give a child zero bags (an empty subset is allowed).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.