Skip to content

2305. Fair Distribution of Cookies 👍

  • Time: $O(k^n)$
  • Space: $O(k + n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int distributeCookies(vector<int>& cookies, int k) {
    int ans = INT_MAX;
    dfs(cookies, 0, k, vector<int>(k), ans);
    return ans;
  }

 private:
  void dfs(const vector<int>& cookies, int s, int k, vector<int>&& children,
           int& ans) {
    if (s == cookies.size()) {
      ans = min(ans, ranges::max(children));
      return;
    }

    for (int i = 0; i < k; ++i) {
      children[i] += cookies[s];
      dfs(cookies, s + 1, k, move(children), ans);
      children[i] -= cookies[s];
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int distributeCookies(int[] cookies, int k) {
    dfs(cookies, 0, k, new int[k]);
    return ans;
  }

  private int ans = Integer.MAX_VALUE;

  private void dfs(int[] cookies, int s, int k, int[] children) {
    if (s == cookies.length) {
      ans = Math.min(ans, Arrays.stream(children).max().getAsInt());
      return;
    }

    for (int i = 0; i < k; ++i) {
      children[i] += cookies[s];
      dfs(cookies, s + 1, k, children);
      children[i] -= cookies[s];
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def distributeCookies(self, cookies: List[int], k: int) -> int:
    ans = math.inf

    def dfs(s: int, children: List[int]) -> None:
      nonlocal ans
      if s == len(cookies):
        ans = min(ans, max(children))
        return

      for i in range(k):
        children[i] += cookies[s]
        dfs(s + 1, children)
        children[i] -= cookies[s]

    dfs(0, [0] * k)
    return ans