Problem

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 the bags of cookies to. All the 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 in the distribution.

Return theminimum unfairness of all distributions.

Examples

Example 1

1
2
3
4
5
6
7

Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: One optimal distribution is [8,15,8] and [10,20]
- The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.

Example 2

1
2
3
4
5
6
7
8

Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7
Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.

Constraints

  • 2 <= cookies.length <= 8
  • 1 <= cookies[i] <= 10^5
  • 2 <= k <= cookies.length

Solution

Method 1 – Backtracking (DFS)

Intuition

Since the number of bags is small (≤8), we can try all possible ways to distribute the bags among the children. For each distribution, we track the maximum cookies any child gets (unfairness) and try to minimize it.

Approach

  1. Use a recursive function to assign each bag to one of the k children.
  2. Maintain an array dist of size k where dist[i] is the total cookies for child i.
  3. For each bag, try giving it to every child and recurse for the next bag.
  4. After all bags are assigned, compute the maximum in dist and update the answer if it’s smaller.
  5. Use pruning: if the current max in dist is already ≥ the best answer so far, stop exploring that branch.

Code

 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 ans = INT_MAX;
    void dfs(vector<int>& cookies, int i, vector<int>& dist, int k) {
        if (i == cookies.size()) {
            ans = min(ans, *max_element(dist.begin(), dist.end()));
            return;
        }
        for (int j = 0; j < k; ++j) {
            dist[j] += cookies[i];
            if (dist[j] < ans) dfs(cookies, i + 1, dist, k);
            dist[j] -= cookies[i];
            if (dist[j] == 0) break;
        }
    }
    int distributeCookies(vector<int>& cookies, int k) {
        vector<int> dist(k, 0);
        dfs(cookies, 0, dist, k);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func distributeCookies(cookies []int, k int) int {
    ans := 1<<31 - 1
    dist := make([]int, k)
    var dfs func(i int)
    dfs = func(i int) {
        if i == len(cookies) {
            max := 0
            for _, v := range dist {
                if v > max { max = v }
            }
            if max < ans { ans = max }
            return
        }
        for j := 0; j < k; j++ {
            dist[j] += cookies[i]
            if dist[j] < ans { dfs(i+1) }
            dist[j] -= cookies[i]
            if dist[j] == 0 { break }
        }
    }
    dfs(0)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    int ans = Integer.MAX_VALUE;
    public int distributeCookies(int[] cookies, int k) {
        int[] dist = new int[k];
        dfs(cookies, 0, dist, k);
        return ans;
    }
    void dfs(int[] cookies, int i, int[] dist, int k) {
        if (i == cookies.length) {
            int max = 0;
            for (int d : dist) max = Math.max(max, d);
            ans = Math.min(ans, max);
            return;
        }
        for (int j = 0; j < k; ++j) {
            dist[j] += cookies[i];
            if (dist[j] < ans) dfs(cookies, i+1, dist, k);
            dist[j] -= cookies[i];
            if (dist[j] == 0) break;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    var ans = Int.MAX_VALUE
    fun distributeCookies(cookies: IntArray, k: Int): Int {
        val dist = IntArray(k)
        fun dfs(i: Int) {
            if (i == cookies.size) {
                ans = minOf(ans, dist.maxOrNull()!!)
                return
            }
            for (j in 0 until k) {
                dist[j] += cookies[i]
                if (dist[j] < ans) dfs(i + 1)
                dist[j] -= cookies[i]
                if (dist[j] == 0) break
            }
        }
        dfs(0)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def distributeCookies(self, cookies: list[int], k: int) -> int:
        ans = float('inf')
        dist = [0] * k
        def dfs(i: int) -> None:
            nonlocal ans
            if i == len(cookies):
                ans = min(ans, max(dist))
                return
            for j in range(k):
                dist[j] += cookies[i]
                if dist[j] < ans:
                    dfs(i + 1)
                dist[j] -= cookies[i]
                if dist[j] == 0:
                    break
        dfs(0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn distribute_cookies(cookies: Vec<i32>, k: i32) -> i32 {
        fn dfs(i: usize, cookies: &Vec<i32>, dist: &mut Vec<i32>, ans: &mut i32, k: usize) {
            if i == cookies.len() {
                *ans = (*ans).min(*dist.iter().max().unwrap());
                return;
            }
            for j in 0..k {
                dist[j] += cookies[i];
                if dist[j] < *ans {
                    dfs(i + 1, cookies, dist, ans, k);
                }
                dist[j] -= cookies[i];
                if dist[j] == 0 { break; }
            }
        }
        let mut ans = i32::MAX;
        let mut dist = vec![0; k as usize];
        dfs(0, &cookies, &mut dist, &mut ans, k as usize);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    distributeCookies(cookies: number[], k: number): number {
        let ans = Infinity;
        const dist = new Array(k).fill(0);
        const dfs = (i: number) => {
            if (i === cookies.length) {
                ans = Math.min(ans, Math.max(...dist));
                return;
            }
            for (let j = 0; j < k; ++j) {
                dist[j] += cookies[i];
                if (dist[j] < ans) dfs(i + 1);
                dist[j] -= cookies[i];
                if (dist[j] === 0) break;
            }
        };
        dfs(0);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k^n), where n is the number of bags and k is the number of children. Each bag can go to any child, so all assignments are tried. Pruning helps but does not change the worst case.
  • 🧺 Space complexity: O(n + k), for the recursion stack and the distribution array.