The power of pruning in backtracking

Posted on

This problem, given the small constraints and the index, requires generating all the possibilities. The recursion becomes exponential quite quickly. Basically at each iteration, it is necessary:

1/ Simulate the addition of the current cookie to the current child, and recursively to the next child

2/ Simulate the addition of the current cookie to the current child, and recursive to the current child

3/ Simulate not adding at all, and move on to the next child

In order to avoid TLE as happened below, add the following pruning rule:

a/ As soon as the injustice is greater than the min, come back and stop the search

That does the trick. The code is at the bottom, well done, ACC.

Fair distribution of cookies – LeetCode

2305. Fair distribution of cookies

Medium

You are given an array of integers cookieswhere cookies[i] indicates the number of cookies in the ith bag. You are also given an integer k which denotes the number of children to be distributed everything bags of cookies to. All cookies in the same bag must go to the same child and cannot be split.

The injustice of a distribution is defined as the maximum total cookies obtained by a single child in the distribution.

Come back the minimum inequity 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
public int DistributeCookies(int[] cookies, int k)
{
    int[] cummulativeCookies = new int[k];
    int retVal = Int32.MaxValue;

    DistributeCookies(cookies,
                        cummulativeCookies,
                        0,
                        new Hashtable(),
                        ref retVal);

    return retVal;
}

private bool DistributeCookies(int[] cookies,
                                int[] cummulativeCookies,
                                int indexK,
                                Hashtable usedCookies,
                                ref int minUnfairness)
{
    if (cummulativeCookies.Max() >= minUnfairness) return false;
    if (indexK >= cummulativeCookies.Length)
    {
        if (usedCookies.Count == cookies.Length)
        {
            /*
            Console.WriteLine("IndexK = {0}", indexK);
            foreach (int i in usedCookies.Keys) Console.Write("{0} ", i);
            Console.WriteLine();
            foreach (int c in cummulativeCookies) Console.Write("{0} ", c);
            Console.WriteLine();
            */

            minUnfairness = Math.Min(minUnfairness, cummulativeCookies.Max());
        }
        return true;
    }

    for (int i = 0; i < cookies.Length; i++)
    {
        if (!usedCookies.ContainsKey(i))
        {
            //Add to the current one, and call for the next ones
            usedCookies.Add(i, true);
            cummulativeCookies[indexK] += cookies[i];
            bool cont = DistributeCookies(cookies,
                                            cummulativeCookies,
                                            indexK + 1,
                                            usedCookies,
                                            ref minUnfairness);
            cummulativeCookies[indexK] -= cookies[i];
            usedCookies.Remove(i);

            if (!cont) break;

            //Add for the current one, and call for the current one
            usedCookies.Add(i, true);
            cummulativeCookies[indexK] += cookies[i];
            cont = DistributeCookies(cookies,
                                        cummulativeCookies,
                                        indexK,
                                        usedCookies,
                                        ref minUnfairness);
            cummulativeCookies[indexK] -= cookies[i];
            usedCookies.Remove(i);

            if (!cont) break;

            //Skip adding it, go to the next one
            cont = DistributeCookies(cookies,
                                        cummulativeCookies,
                                        indexK + 1,
                                        usedCookies,
                                        ref minUnfairness);

            if (!cont) break;
        }
    }

    return true;
}

Leave a Reply

Your email address will not be published.