Partition to K Equal Sum Subsets

This approach uses a straightforward brute-force backtracking algorithm. The core idea is to try and place each number from the input array nums into one of the k available subsets. The recursion explores every possible assignment of numbers to subsets until a valid partition is found or all possibilities are exhausted.

• Calculate the total sum of nums. If it's not divisible by k, or if k is non-positive, return false.
• Calculate the targetSum for each subset, which is totalSum / k.
• Sort the input array nums in descending order. This is an optimization that helps in pruning the search space faster by trying to place larger numbers first.
• Create an array subsetSums of size k to keep track of the current sum of each of the k subsets, initialized to all zeros.
• Implement a recursive backtracking function, say backtrack(index), which tries to place the number nums[index].
• Base Case: If index equals nums.length, it means all numbers have been successfully placed into subsets, so we return true.
• Recursive Step: For the number nums[index], iterate through the k subsets. For each subset j, if adding nums[index] does not exceed targetSum:
  • Add nums[index] to subsetSums[j].
  • Make a recursive call backtrack(index + 1).
  • If the recursive call returns true, a solution is found, so propagate true.
  • If not, backtrack by subtracting nums[index] from subsetSums[j] and try the next subset.
• An important optimization: If placing nums[index] into an empty subset j (where subsetSums[j] == 0) fails, we can stop trying to place it in any other empty subset, as it would lead to a symmetric, failing search path.
• If the loop finishes without finding a suitable subset for nums[index], return false.
• The initial call to start the process is backtrack(0).

In this method, we first perform some preliminary checks. The total sum of all numbers in nums must be perfectly divisible by k; otherwise, it's impossible to form k subsets with equal sums. The required sum for each subset is targetSum = totalSum / k. Additionally, no single number can be larger than this targetSum.

The main logic resides in a recursive function that takes the current index of the number to be placed as an argument. This function iterates through the k subsets and attempts to add the current number to one of them. If adding the number doesn't violate the targetSum constraint, it makes a recursive call for the next number. If the subsequent recursive call finds a solution, we're done. If not, we backtrack by removing the number and trying the next available subset.

To make this brute-force approach slightly more tenable, we can introduce optimizations. Sorting the input array nums in descending order is a powerful heuristic. By attempting to place larger numbers first, we are more likely to hit the targetSum constraint early, which helps to prune the search tree and reduce the number of recursive calls.

import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (k <= 0 || totalSum % k != 0) {
            return false;
        }
        int targetSum = totalSum / k;
        
        // Sort in descending order for optimization
        Arrays.sort(nums);
        for(int i = 0, j = nums.length - 1; i < j; i++, j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        if (nums[0] > targetSum) return false;

        return backtrack(nums, 0, new int[k], targetSum);
    }

    private boolean backtrack(int[] nums, int index, int[] subsetSums, int targetSum) {
        if (index == nums.length) {
            return true;
        }

        int currentNum = nums[index];
        for (int i = 0; i < subsetSums.length; i++) {
            if (subsetSums[i] + currentNum <= targetSum) {
                subsetSums[i] += currentNum;
                if (backtrack(nums, index + 1, subsetSums, targetSum)) {
                    return true;
                }
                subsetSums[i] -= currentNum; // Backtrack
                // Optimization: If this subset was empty, and it failed, 
                // no need to try other empty subsets.
                if (subsetSums[i] == 0) break;
            }
        }
        return false;
    }
}