Leetcode daily question (2305. fair distribution of cookies)

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 the minimum unfairness of all distributions.

Example 1:

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:

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] <= 105
• 2 <= k <= cookies.length

---

From the perspective of cookies , Every bag of biscuits must belong to a child , We enumerate each distribution to take the minimum and maximum inequality .

note: Personally realize that memory allocation not only consumes memory space , It also takes time ( It seems like bullshit , But the measured time consumption is really a little big ), Same method , My method is to copy a new copy of the current state array, and then modify it and transfer it to the next layer , The result is timeout , But as they say backtracking Methods , Pass the reference and it will pass smoothly

---

impl Solution {
    
    fn backtracking(cookies: &Vec<i32>, k: i32, i: usize, stat: &mut Vec<i32>) -> i32 {
    
        if i == cookies.len() {
    
            return *stat.iter().max().unwrap();
        }
        let mut ans = i32::MAX;
        for n in 0..k as usize {
    
            stat[n] += cookies[i];
            ans = ans.min(Solution::backtracking(cookies, k, i + 1, stat));
            stat[n] -= cookies[i];
        }
        ans
    }
    pub fn distribute_cookies(cookies: Vec<i32>, k: i32) -> i32 {
    
        Solution::backtracking(&cookies, k, 0, &mut vec![0; k as usize])
    }
}