Fair distribution of cookies

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

69.8% acceptance

Feb 25, 2026

2729

127

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 bags to. All 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. Return the minimum unfairness of all distributions.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distribute_cookies(cookies: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let mut children = vec![0i32; k];
    let mut ans = i32::MAX;
    Self::dfs(&cookies, &mut children, 0, &mut ans);
    ans
  }

  fn dfs(cookies: &[i32], children: &mut Vec<i32>, idx: usize, ans: &mut i32) {
    if idx == cookies.len() {
      let mx = *children.iter().max().unwrap();
      if mx < *ans {
        *ans = mx;
      }
      return;
    }
    let mut seen = std::collections::HashSet::new();
    for i in 0..children.len() {
      if seen.contains(&children[i]) {
        continue;
      }
      seen.insert(children[i]);
      children[i] += cookies[idx];
      if children[i] < *ans {
        Self::dfs(cookies, children, idx + 1, ans);
      }
      children[i] -= cookies[idx];
    }
  }
}