LeetCode 2305 - Fair Distribution of Cookies

The problem asks us to distribute a set of cookie bags among k children such that the unfairness of the distribution is minimized. Here, unfairness is defined as the maximum total number of cookies any single child receives.

leetcodemediumarraydynamic-programmingbacktrackingbit-manipulationbitmask

LeetCode Problem 2305

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem asks us to distribute a set of cookie bags among k children such that the unfairness of the distribution is minimized. Here, unfairness is defined as the maximum total number of cookies any single child receives.

The input consists of an array cookies where cookies[i] represents the number of cookies in the i-th bag, and an integer k representing the number of children. Each cookie bag must be assigned entirely to a single child, so splitting is not allowed. The goal is to compute the minimum possible value of the maximum sum of cookies received by any child after distributing all bags.

Constraints indicate that cookies.length is small (at most 8), which suggests that an exhaustive or combinatorial approach is feasible. Each cookie bag can contain up to 10^5 cookies, and k can be as small as 2 or as large as the number of cookie bags.

Important edge cases include situations where the number of children equals the number of bags, where one child may end up with multiple high-value bags, or where all bags have equal cookies.

Approaches

A brute-force approach is to consider every possible assignment of each cookie bag to one of the k children. Since each bag can go to any child independently, there are k^n possible assignments, where n is the number of cookie bags. For each assignment, we compute the total cookies each child receives and track the maximum. The minimum of all these maxima is the answer. While correct, this approach grows exponentially and becomes impractical for larger n (though n <= 8 keeps it manageable here).

The key insight for optimization is backtracking with pruning. We recursively assign bags to children while maintaining an array of current cookie totals per child. If at any point the current maximum exceeds a known minimum unfairness, we can prune that branch since continuing cannot improve the result. This avoids exploring all k^n combinations in practice.

Approach Time Complexity Space Complexity Notes
Brute Force O(k^n * n) O(n) Try all assignments of bags to children, calculate max unfairness each time
Optimal (Backtracking with Pruning) O(k^n) in worst case, faster in practice O(k + n) Recursively assign bags with pruning based on current maximum

Algorithm Walkthrough

  1. Initialize an array totals of length k with zeros to track the current sum of cookies for each child.
  2. Define a recursive function dfs(index) where index represents the current cookie bag to assign.
  3. If index == n, all bags are assigned. Compute the maximum value in totals and update the global minimum unfairness if it is smaller.
  4. For each child i from 0 to k-1, assign cookies[index] to child i and update totals[i].
  5. Before recursing, check if totals[i] is already greater than or equal to the current minimum unfairness. If so, skip this branch.
  6. Recurse to dfs(index + 1).
  7. After recursion, backtrack by removing cookies[index] from totals[i].
  8. Continue this for all children, exploring all feasible distributions.

Why it works: The backtracking approach explores all feasible distributions while pruning paths that cannot improve the solution. This ensures we find the minimum unfairness. Each leaf of the recursion tree corresponds to a complete assignment of all cookie bags.

Python Solution

from typing import List

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        n = len(cookies)
        totals = [0] * k
        self.min_unfairness = float('inf')

        def dfs(index: int):
            if index == n:
                self.min_unfairness = min(self.min_unfairness, max(totals))
                return
            for i in range(k):
                totals[i] += cookies[index]
                if totals[i] < self.min_unfairness:
                    dfs(index + 1)
                totals[i] -= cookies[index]
                if totals[i] == 0:
                    break

        dfs(0)
        return self.min_unfairness

This Python solution uses a recursive depth-first search. The totals array keeps track of the sum of cookies each child has. The if totals[i] == 0: break line is an optimization that avoids redundant symmetric assignments where multiple children have zero cookies.

Go Solution

func distributeCookies(cookies []int, k int) int {
    n := len(cookies)
    totals := make([]int, k)
    minUnfairness := 1 << 60

    var dfs func(int)
    dfs = func(index int) {
        if index == n {
            maxTotal := 0
            for _, t := range totals {
                if t > maxTotal {
                    maxTotal = t
                }
            }
            if maxTotal < minUnfairness {
                minUnfairness = maxTotal
            }
            return
        }
        for i := 0; i < k; i++ {
            totals[i] += cookies[index]
            if totals[i] < minUnfairness {
                dfs(index + 1)
            }
            totals[i] -= cookies[index]
            if totals[i] == 0 {
                break
            }
        }
    }

    dfs(0)
    return minUnfairness
}

In Go, the main differences are the use of slices for totals and integer constants for infinity. The recursion logic is identical to Python.

Worked Examples

Example 1: cookies = [8,15,10,20,8], k = 2

Index totals before assign bag totals after max(totals)
0 [0,0] 8 -> child 0 [8,0] 8
1 [8,0] 15 -> child 1 [8,15] 15
2 [8,15] 10 -> child 0 [18,15] 18
3 [18,15] 20 -> child 1 [18,35] 35 (pruned)
... ... ... ... ...
Final [31,30] - - 31

Example 2: cookies = [6,1,3,2,2,4,1,2], k = 3

The algorithm will explore assignments but prune branches exceeding current minimum. The optimal distribution is [6,1], [3,2,2], [4,1,2] resulting in max total 7.

Complexity Analysis

Measure Complexity Explanation
Time O(k^n) In the worst case, each of n bags can go to any of k children
Space O(k + n) O(k) for totals array, O(n) for recursion stack

Although the theoretical time complexity is exponential, pruning reduces actual computation for typical inputs.

Test Cases

# Provided examples
assert Solution().distributeCookies([8,15,10,20,8], 2) == 31  # example 1
assert Solution().distributeCookies([6,1,3,2,2,4,1,2], 3) == 7  # example 2

# Edge cases
assert Solution().distributeCookies([1,1], 2) == 1  # smallest input
assert Solution().distributeCookies([5,5,5,5], 4) == 5  # one bag per child
assert Solution().distributeCookies([10,20,30], 2) == 30  # uneven distribution
assert Solution().distributeCookies([1,2,3,4,5,6,7,8], 2) == 20  # maximal length
Test Why
[8,15,10,20,8], k=2 Basic scenario from example 1
[6,1,3,2,2,4,1,2], k=3 Basic scenario from example 2
[1,1], k=2 Minimal input
[5,5,5,5], k=4 Each child gets one bag, checks trivial distribution
[10,20,30], k=2 Uneven distribution forces max sum selection
[1,2,3,4,5,6,7,8], k=2 Maximal number of bags tests recursion depth

Edge Cases

One important edge case is when the number of children equals the number of cookie bags. Each child receives exactly one bag, so the minimum unfairness is the maximum value in the cookies array. The algorithm handles this naturally since each leaf in the recursion tree will assign one bag per child.

Another edge case is when one child might need to take multiple high-value bags to balance the unfairness. Without pruning, the naive approach would explore all combinations unnecessarily. The implemented pruning ensures that branches where the current maximum exceeds the known minimum are skipped.

A third edge case is when several cookie bags have the same value. This can introduce symmetry in assignments. The optimization that breaks the loop when `