You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith 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.
Example 1:
Input: cookies = [8,15,10,20,8], k = 2 Output: 31 Explanation: One optimal distribution is [8,15,8] and [10,20] - The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies. - The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies. The unfairness of the distribution is max(31,30) = 31. It can be shown that there is no distribution with an unfairness less than 31.
Example 2:
Input: cookies = [6,1,3,2,2,4,1,2], k = 3 Output: 7 Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2] - The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies. - The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies. - The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies. The unfairness of the distribution is max(7,7,7) = 7. It can be shown that there is no distribution with an unfairness less than 7.
Constraints:
2 <= cookies.length <= 81 <= cookies[i] <= 1052 <= k <= cookies.lengthProblem 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.
This approach leverages backtracking to explore all possible ways of distributing the bags of cookies among the children. We utilize a recursive function to attempt to give each bag of cookies to any of the available children. At each step, we update the total cookies received by the child to whom the current bag is assigned. The goal is to minimize the maximum number of cookies any child receives, known as unfairness.
This solution uses recursion to assign each cookie bag to one of the k children. Each recursive call explores adding the current cookie bag to any child's current collection. The recursion depth corresponds to processing each cookie bag. Once all bags are distributed, it computes the maximum cookies received by any child in that distribution (unfairness). The recursive solution uses backtracking to explore different paths and aims to minimize the maximum unfairness across all potential distributions.
Time Complexity: O(k^n), where n is the number of cookie bags and k is the number of children. The solution explores every distribution possibility.
Space Complexity: O(k + n), due to the recursion stack and the distribution array.
This approach uses bitmasking in conjunction with dynamic programming to keep track of all combinations of cookie distributions among k children. We aim to optimize processing by encoding choices using bitmasks to represent different subsets of cookies. This method alleviates computational overhead by avoiding permutation/combination evaluation via iterative states and sub-state record tracking. We leverage a DP technique where dp[mask][children] represents the minimum unfairness achievable assigning the selected cookie combination (mask) across given children.
The C solution here employs a 2D array to track the minimal unfairness through a combination of subsets and children allocation states. Utilizes numerous possible sub-states via masks representing cookie allocation realization across valid compartments. Varied subsets are computed iteratively ensuring that the unnecessary re-evaluation of states is avoided through DP caching.
Time Complexity: O(n * 2^n * k), dealing with both subset and child assignment constraints.
Space Complexity: O(2^n * k), necessary for complete subset and branch caching.
First, we sort the array cookies in descending order (to reduce the number of searches), and then create an array cnt of length k to store the number of cookies each child gets. Also, we use a variable ans to maintain the current minimum degree of unfairness, initialized to a very large value.
Next, we start from the first snack pack. For the current snack pack i, we enumerate each child j. If the cookies cookies[i] in the current snack pack are given to child j, making the degree of unfairness greater than or equal to ans, or the number of cookies the current child already has is the same as the previous child, then we don't need to consider giving the cookies in the current snack pack to child j, just skip it (pruning). Otherwise, we give the cookies cookies[i] in the current snack pack to child j, and then continue to consider the next snack pack. When we have considered all the snack packs, we update the value of ans, then backtrack to the previous snack pack, and continue to enumerate which child to give the cookies in the current snack pack to.
Finally, we return ans.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(k^n), where n is the number of cookie bags and k is the number of children. The solution explores every distribution possibility. |
| Dynamic Programming via Bitmasking | Time Complexity: O(n * 2^n * k), dealing with both subset and child assignment constraints. |
| Backtracking + Pruning | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(k^n) | O(n) | Best practical solution when number of cookie bags is small. Easy to implement and preferred in interviews. |
| Dynamic Programming with Bitmask | O(k * 3^n) | O(k * 2^n) | Useful when practicing subset DP or when you want a structured state-based solution. |
Fair Distribution of Cookies | Khandani Backtracking Template | Leetcode-2305 | Explanation | Coding • codestorywithMIK • 16,942 views views
Watch 9 more video solutions →Practice Fair Distribution of Cookies with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor