< Back 2305. Fair Distribution of Cookies We're given a list of cookies and k, the number of children we have to evenly distribute the cookies to. The problem statement provided isn't the greatest - there are invalid distributions, that being that all children have to be given at least one bag of cookies. We're asked to find the minimum unfairness of all possible distributions, where unfairness is measured by the maximum sum of cookies provided to a single child. Using backtracking, we can traverse our choices to distribute cookies to children like a graph. For each node in the graph, we have k neighbors representing the child we give a bag of cookies to. During each step in the traversal of this graph, we maintain the bag of cookies we're distributing, and increment after a child is chosen. Once we've distributed all the cookies, such that i == n, we take the maximum unfairness and compare it to our currently running answer, keeping the minimum of the two values. To decrease our search space, we realize we're going to encounter situations in which we've distributed too many cookies to one child, and there are not enough cookies left for the remaining children. To avoid searching paths where this occurs, we keep track of how many children don't have cookies, and how many cookies we have left. During the recursion, if we realize that the number of children without cookies is greater than the number of cookies remaining, we backtrack - there's no point in traversing this path. Finally, we decrease our search space by only traversing paths where the number of cookies a child has is less than the current minimum unfairness we've seen so far. That eliminates paths later in the traversal where our answer probably won't be updated. The solution is as follows: class Solution: def distributeCookies(self, cookies: List[int], k: int) -> int: self.ans, child, n = float("inf"), [0] * k, len(cookies) def backtrack(i: int, z: int) -> None: if n - i < z: return if i == n: self.ans = min(self.ans, max(child)) return for j in range(k): z -= int(child[j] == 0) child[j] += cookies[i] if child[j] < self.ans: backtrack(i + 1, z) child[j] -= cookies[i] z += int(child[j] == 0) backtrack(0, k) return self.ans _ Time Complexity: O(k^n) - We make k choices during each step of the search, and we have to distribute n cookies. _ Space Complexity: O(k + n) - n levels of recursion will occur, and we store k space to keep track of the cookies distributed.