Backtracking - Fair Distribution of Cookies

You have k children and n bags of cookies. Distribute all bags among k children such that the maximum number of cookies any child gets is minimized. Return that minimum maximum.

Input: cookies = [8,15,10,20,8], k = 2 → Output: 31

Input: cookies = [6,1,3,2,2,4,1,2], k = 3 → Output: 7

Use backtracking over all assignments. Try giving each cookie bag to each child. Prune branches where a child's current total already exceeds our best answer.

Maintain an array children[] of size k tracking each child's total.
At each bag index, try assigning it to each child.
After assigning, recurse to the next bag; then backtrack.
When all bags are distributed, update the global minimum with max(children[]).

class Solution { int ans = Integer.MAX_VALUE; public int distributeCookies(int[] cookies, int k) { backtrack(cookies, new int[k], 0); return ans; } private void backtrack(int[] cookies, int[] children, int idx) { if (idx == cookies.length) { int max = 0; for (int c : children) max = Math.max(max, c); ans = Math.min(ans, max); return; } for (int i = 0; i < children.length; i++) { children[i] += cookies[idx]; if (children[i] < ans) backtrack(cookies, children, idx + 1); children[i] -= cookies[idx]; if (children[i] == 0) break; // symmetry pruning } } }

Time Complexity: O(k^n) worst case with pruning
Space Complexity: O(k + n) — children array + stack