Code Implementation

class Solution:
    def canPartitionKSubsets(self, nums, k):
        total = sum(nums)
        if total % k != 0:
            return False
        target = total // k
        nums.sort(reverse=True)
        if nums[0] > target:
            return False
        used = [False] * len(nums)
        
        def backtrack(start, k, curr_sum):
            if k == 1:
                return True
            if curr_sum == target:
                return backtrack(0, k - 1, 0)
            for i in range(start, len(nums)):
                if not used[i] and curr_sum + nums[i] <= target:
                    used[i] = True
                    if backtrack(i + 1, k, curr_sum + nums[i]):
                        return True
                    used[i] = False
            return False
        
        return backtrack(0, k, 0)
      

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % k != 0) return false;
        int target = total / k;
        sort(nums.rbegin(), nums.rend());
        if (nums[0] > target) return false;
        vector<bool> used(nums.size(), false);
        
        function<bool(int, int, int)> backtrack = [&](int start, int k, int curr_sum) {
            if (k == 1) return true;
            if (curr_sum == target) return backtrack(0, k - 1, 0);
            for (int i = start; i < nums.size(); ++i) {
                if (!used[i] && curr_sum + nums[i] <= target) {
                    used[i] = true;
                    if (backtrack(i + 1, k, curr_sum + nums[i]))
                        return true;
                    used[i] = false;
                }
            }
            return false;
        };
        
        return backtrack(0, k, 0);
    }
};
      

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int n : nums) total += n;
        if (total % k != 0) return false;
        int target = total / k;
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n - 1] > target) return false;
        boolean[] used = new boolean[n];
        
        return backtrack(nums, used, 0, k, 0, target);
    }
    
    private boolean backtrack(int[] nums, boolean[] used, int start, int k, int currSum, int target) {
        if (k == 1) return true;
        if (currSum == target) return backtrack(nums, used, 0, k - 1, 0, target);
        for (int i = start; i < nums.length; i++) {
            if (!used[i] && currSum + nums[i] <= target) {
                used[i] = true;
                if (backtrack(nums, used, i + 1, k, currSum + nums[i], target))
                    return true;
                used[i] = false;
            }
        }
        return false;
    }
}
      

var canPartitionKSubsets = function(nums, k) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % k !== 0) return false;
    const target = total / k;
    nums.sort((a, b) => b - a);
    if (nums[0] > target) return false;
    const used = Array(nums.length).fill(false);

    function backtrack(start, k, currSum) {
        if (k === 1) return true;
        if (currSum === target) return backtrack(0, k - 1, 0);
        for (let i = start; i < nums.length; i++) {
            if (!used[i] && currSum + nums[i] <= target) {
                used[i] = true;
                if (backtrack(i + 1, k, currSum + nums[i])) return true;
                used[i] = false;
            }
        }
        return false;
    }

    return backtrack(0, k, 0);
};
      

Problem Description

Given an array of positive integers nums and an integer k, the task is to determine if it is possible to partition nums into k non-empty subsets whose sums are all equal.

• Each element in nums must be used exactly once in one of the subsets.
• No element can be reused in multiple subsets.
• There may be multiple ways to partition, but you only need to determine if at least one valid partition exists.
• Constraints often ensure 1 <= k <= len(nums) and 1 <= nums[i] <= 10^4.

Return true if such a partition is possible, or false otherwise.

Thought Process

At first glance, the problem looks similar to the classic subset sum or partition problem, but with the added twist of dividing into k equal groups. The brute-force approach would be to try all possible ways to assign elements to k groups and check if each group sums to the same value, but this quickly becomes infeasible as the array grows.

To optimize, we consider:

• First, the total sum must be divisible by k; otherwise, it's impossible.
• We can try to build up each subset incrementally, using backtracking to explore possibilities.
• Sorting the array in descending order helps by placing bigger numbers first, which can help fail faster if a solution isn't possible.
• We use a boolean array to mark which elements are already used in subsets, ensuring no reuse.

The main challenge is efficiently exploring the combinations without redundant work, which leads us to recursive backtracking with pruning.

Solution Approach

The solution uses a recursive backtracking approach with several optimizations:

1. Check Divisibility:
   • Calculate the total sum of nums. If it's not divisible by k, return false immediately.
2. Determine Target Subset Sum:
   • The sum each subset must reach is target = total_sum / k.
3. Sort the Array:
   • Sort nums in descending order to put large numbers first, which helps prune impossible branches quickly.
4. Backtracking Function:
   • Use a recursive function to try to fill each subset.
   • Use a used array to keep track of which elements are already included in a subset.
   • If the current subset sum reaches target, start filling the next subset.
   • If all subsets but one are filled, the last must be correct (since total sum matches).
   • Try to add each unused number to the current subset, and recursively continue.
   • If adding a number exceeds the target, skip it (pruning).
   • Backtrack by marking the number as unused if the path doesn't lead to a solution.
5. Return the Result:
   • If a valid partition is found, return true; otherwise, return false.

This method efficiently explores only valid assignments, avoiding redundant or impossible paths.

Example Walkthrough

Example: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

• Total sum = 20; 20 / 4 = 5, so each subset must sum to 5.
• Sort: [5, 4, 3, 3, 2, 2, 1]
• Start forming subsets:
• First subset: take 5 (used), sum = 5. Move to next subset.
• Second subset: start with 4, need 1 more. Use 1 (used), sum = 5.
• Third subset: start with 3, need 2 more. Use 2 (used), sum = 5.
• Fourth subset: left with 3 and 2 (both unused), sum = 5.
• All elements used exactly once. All subsets sum to 5. Return true.

The backtracking explores possible combinations, but the sorted order and pruning prevent unnecessary work.

Time and Space Complexity

• Brute-force:
  • Would try all possible ways to assign n elements to k groups, leading to O(k^n) time complexity.
• Optimized Backtracking:
  • Still exponential in the worst case, but much faster due to pruning and early exits.
  • Typically, time is O(k * 2^n), since each number can be assigned to a subset, but with effective pruning, real-world performance is much better.
  • Space complexity is O(n) for the used array and recursion stack.

Summary

The "Partition to K Equal Sum Subsets" problem is a challenging variation of the subset sum problem. By checking divisibility, sorting, and using recursive backtracking with pruning, we can efficiently determine if a valid partition exists. The key insight is to build each subset incrementally, avoid redundant work, and exit early when impossible paths are detected. This makes the solution both elegant and practical for moderate input sizes.