Leetcode Problem 2305. Fair Distribution of Cookies

2305. Fair Distribution of Cookies

Leetcode Solutions

Backtracking to Minimize Maximum Unfairness

  1. Initialize an array distribute of length k with all zeros, representing the total cookies each child has received.
  2. Define a recursive function dfs(i, zero_count) to distribute the ithi^{th} cookie:
    • If n - i < zero_count, return float('inf') as the distribution is invalid.
    • If i == n, return the maximum value in distribute as the unfairness of this distribution.
    • Otherwise, set answer to float('inf').
  3. Iterate through each child j in distribute:
    • Add cookies[i] to distribute[j].
    • If distribute[j] was 0 before adding, decrement zero_count.
    • Call dfs(i + 1, zero_count) and update answer with the minimum unfairness.
    • Remove cookies[i] from distribute[j] (backtrack).
    • If distribute[j] is 0 after removing, increment zero_count.
  4. Return the result of dfs(0, k) as the final answer.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...