Partition To K Equal Sum Subsets - Leetcode Solution

The Partition to K Equal Sum Subsets problem on LeetCode asks us to divide an input array into k non-empty subsets with equal sums. It returns True if we can form k such subsets and False otherwise.

Let's take the following example:

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

We need to check if we can divide the array into 4 subsets with equal sums.

One intuitive approach to solve this problem is to use backtracking. We can start with an empty subset and try adding each number from the input array to it. After adding a number, we check if the current subset has reached the required sum. If yes, we move on to the next subset, otherwise we continue searching for numbers to add.

However, this approach can be inefficient as we will be checking all possible combinations of subsets. To optimize this approach, we can use a few pruning techniques:

1. If we are not able to form a subset after processing all the numbers in the input array, we can return False as it is not possible to form k subsets with equal sums.
2. We can sort the input array in descending order. This can help us find the larger numbers first and place them in the subsets with lower sums. This reduces the number of subsets we need to create and also reduces the amount of backtracking needed.
3. We can use a visited array to keep track of the numbers we have already used in a subset. This can help us avoid duplicate combinations of subsets.

Here's the code for the solution:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total_sum = sum(nums)
        if k <= 0 or total_sum % k != 0:
            return False
        
        target_sum = total_sum // k
        nums.sort(reverse=True)
        visited = [False] * len(nums)
        
        def backtrack(current_sum, subset_count, start_index):
            if subset_count == k:
                return True
            if current_sum == target_sum:
                return backtrack(0, subset_count + 1, 0)
            
            for i in range(start_index, len(nums)):
                if not visited[i] and current_sum + nums[i] <= target_sum:
                    visited[i] = True
                    if backtrack(current_sum + nums[i], subset_count, i + 1):
                        return True
                    visited[i] = False
            
            return False
        
        return backtrack(0, 0, 0)

In this code, we first check if k is less than or equal to 0 or if the total sum of the input array is not divisible by k. If any of these conditions is true, we return False as it is not possible to form k subsets with equal sums.

We then calculate the target sum that each subset should have and sort the input array in descending order.

We define a backtrack function that takes in three parameters - the current sum of the subset, the number of subsets already formed and the index of the next number to consider.

In the backtrack function, we first check if we have formed k subsets. If yes, we can return True as we have found a valid solution. If the current sum is equal to the target sum, we move on to the next subset and start adding numbers from the beginning.

We then loop through the input array, starting from the start_index. We check if the current number has not been used in a previous subset and if adding it to the current sum will not exceed the target sum. If both these conditions are satisfied, we mark the number as visited and recursively call the backtrack function with the updated sum and the index of the next number to consider.

If the recursive call returns True, we have found a valid solution and can return True. However, we need to make sure to mark the number as unvisited before backtracking.

If none of the numbers result in a valid solution, we return False as no valid solution exists.

Finally, we call the backtrack function with the initial parameters and return its result.

1