The power of pruning in backtracking V

Backtracking is a great technique in algorithms, but it needs to be accompanied by aggressive pruning or else it may quickly become intractable. This was an interesting problem, and the small input numbers (10^5 and k<=5) tells me that the authors knew that this could quickly become intractable, even with pruning. The pruning here primarily happens in two occasions: first during the base case (k==0), second when the product becomes larger than n. Comparing my solution with Sonnet 4's and ChatGPT 5's (and I gave them all the hints too), there is a small gain in my solution compared to theirs. It was surprising to see that Anthropic's one didn't make use of pruning as well as mine's or ChatGPT 5's. Code is down below, cheers, ACC.

Balanced K-Factor Decomposition - LeetCode

Given two integers n and k, split the number n into exactly k positive integers such that the product of these integers is equal to n.

Return any one split in which the maximum difference between any two numbers is minimized. You may return the result in any order.

 

Example 1:

Input: n = 100, k = 2

Output: [10,10]

Explanation:

The split [10, 10] yields 10 * 10 = 100 and a max-min difference of 0, which is minimal.

Example 2:

Input: n = 44, k = 3

Output: [2,2,11]

Explanation:

• Split [1, 1, 44] yields a difference of 43
• Split [1, 2, 22] yields a difference of 21
• Split [1, 4, 11] yields a difference of 10
• Split [2, 2, 11] yields a difference of 9

Therefore, [2, 2, 11] is the optimal split with the smallest difference 9.

 

Constraints:

• 4 <= n <= 105
• 2 <= k <= 5
• k is strictly less than the total number of positive divisors of n.

public class Solution {
    //Medium LC 9/1/25
    public int[] MinDifference(int n, int k)
    {
        int[] divisors = Divisors(n);

        //Debug
        /*
        Console.WriteLine("Divisors({0}):", n);
        foreach (int d in divisors)
            Console.Write("{0} ", d);
        Console.ReadLine();
        */

        int minDiff = Int32.MaxValue;
        int[] retVal = null;

        CalculateBalancedKFactor(n,
                                 k,
                                 divisors,
                                 0,
                                 1,
                                 new List(),
                                 ref minDiff,
                                 ref retVal);

        return retVal;
    }

    private void CalculateBalancedKFactor(int n,
                                          int k,
                                          int[] divisors,
                                          int start,
                                          int product,
                                          List picked,
                                          ref int minDiff,
                                          ref int[] retVal)
    {
        //Debug
        /*
        Console.WriteLine("Picked: ");
        foreach (int p in picked)
            Console.Write("{0} ", p);
        Console.WriteLine();
        Console.WriteLine("Product: {0}", product);
        Console.ReadLine();
        */

        //Base
        if (k == 0)
        {
            if (product == n)
            {
                int diff = picked[0] - picked[picked.Count - 1];

                //Debug
                /*
                Console.WriteLine("Diff = {0}", diff);
                Console.WriteLine("Min Diff = {0}", minDiff);
                Console.ReadLine();
                */

                if (diff < minDiff)
                {
                    minDiff = diff;
                    retVal = new int[picked.Count];
                    for (int i = 0; i < picked.Count; i++)
                        retVal[i] = picked[i];
                }
            }
            return;
        }

        //Prune
        if (product > n) return;

        //Induction
        for (int i = start; i < divisors.Length; i++)
        {
            picked.Add(divisors[i]);
            CalculateBalancedKFactor(n,
                                     k - 1,
                                     divisors,
                                     i,
                                     product * divisors[i],
                                     picked,
                                     ref minDiff,
                                     ref retVal);
            picked.RemoveAt(picked.Count - 1);
        }
    }

    private int[] Divisors(int n)
    {
        List divisors = new List();

        for (int d = n; d > 0; d--)
        {
            if (n % d == 0)
                divisors.Add(d);
        }

        return divisors.ToArray();
    }
}