2305. Fair Distribution of Cookies

[box-lin]

Time: O(k^n), each level of recusive stack at most of k.
Space: O(k+n), recursive stack at most depth of n.

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        def dfs(i):
            nonlocal res
            if i >= len(cookies):
                curmax = max(acc)
                res = min(res, curmax) 
                return
            # cut the recursion
            if max(acc) >= res:
                return
            # for a bag of cookie we have k choices (children) to distribute.
            for j in range(k):
                acc[j] += cookies[i]
                dfs(i+1)
                acc[j] -= cookies[i]
        res = math.inf
        acc = [0] * k
        dfs(0)
        return res