<p>You are given an integer array <code>cookies</code>, where <code>cookies[i]</code> denotes the number of cookies in the <code>i<sup>th</sup></code> bag. You are also given an integer <code>k</code> that denotes the number of children to distribute <strong>all</strong> the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.</p>

<p>The <strong>unfairness</strong> of a distribution is defined as the <strong>maximum</strong> <strong>total</strong> cookies obtained by a single child in the distribution.</p>

<p>Return <em>the <strong>minimum</strong> unfairness of all distributions</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cookies = [8,15,10,20,8], k = 2
<strong>Output:</strong> 31
<strong>Explanation:</strong> One optimal distribution is [8,15,8] and [10,20]
- The 1<sup>st</sup> child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2<sup>nd</sup> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cookies = [6,1,3,2,2,4,1,2], k = 3
<strong>Output:</strong> 7
<strong>Explanation:</strong> One optimal distribution is [6,1], [3,2,2], and [4,1,2]
- The 1<sup>st</sup> child receives [6,1] which has a total of 6 + 1 = 7 cookies.
- The 2<sup>nd</sup> child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3<sup>rd</sup> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= cookies.length &lt;= 8</code></li>
	<li><code>1 &lt;= cookies[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= k &lt;= cookies.length</code></li>
</ul>

"""
This problem cannot be solved in Greedy Way, always picking the current least and
incrementing that with the cookie will not work in some cases.
So we need to try backtracking.
Form the tree in your head, how does it look?
"""
class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        # Initialize an array to keep track of each child's cookie sum
        subset = [0] * k
        res = float('inf')
        
        def backtrack(i):
            nonlocal res
            if i == len(cookies):
                # Update the minimum unfairness found
                res = min(res, max(subset))
                return
            
            # Try to give the i-th cookie to each child
            for j in range(k):
                subset[j] += cookies[i]
                if subset[j] < res:
                    backtrack(i + 1)
                subset[j] -= cookies[i]
        
        backtrack(0)
        return res
"""
class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        res = [0] * k
        maxUnfairness = 0
        cookies = [(cookie * -1) for cookie in cookies]
        heapq.heapify(cookies)
        i = 0
        while cookies:
            cookie = -heapq.heappop(cookies)
            # Find the person with the least cookies so far
            i = res.index(min(res))
            res[i] += cookie
            #maxUnfairness = max(maxUnfairness, res[i])

        return max(res)
"""
1904