Make K Subarray Sums Equal - Leetcode Solution

Problem Statement: Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Solution: The problem can be solved using recursion and backtracking. To divide the array into k subsets with equal sum, we need to find the value of the sum that each subset should have.

1. Check if the total sum of the array is divisible by k. If not return false.

2. Sort the input array in decreasing order. We sort the array in descending order to check the biggest element that can be added to the current sum in subsets.

3. Create an empty array of size k, which will store the k subsets.

4. Define a recursive function named ‘helper’ with four parameters: array nums, an integer target_sum, an array subset, and an index i that represents the current index of nums being considered.

The function targets to create k subsets, which have the same sum target_sum (i.e., target_sum = sum(nums) / k).

a. Base case: If i = n and all subsets have sum equal to target_sum, return true.

b. If the sum of the current subset equals the target_sum, start building the next subset with i=0.

c. For the i-th index element, with value nums[i]:

i. if nums[i] > 0, check whether we can add nums[i] to the current subset without exceeding the target_sum.

ii. Otherwise, if nums[i] < 0, check whether we can add nums[i] to the current subset without going below the target_sum.

iii. If the above conditions are met, add nums[i] to the current subset and move on to the next index i+1. If nums[i] cannot be added to the current subset, backtrack and check the next value in nums[i+1].

5. Call the ‘helper’ function with initial values: array nums, target_sum = sum(nums) / k, empty array subset, and index i = 0.

6. If the function returns true, then we can divide the array into k equal subsets, return true, else false.

The time complexity of this approach is O(k * 2^n), where n is the size of the input array nums. The space complexity is O(n + k) for the recursion stack and subset array.

Python Code:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # Step 1
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        
        # Step 2
        nums.sort(reverse=True)
        
        # Step 3
        subset_sum = total_sum // k
        subsets = [0] * k
        
        # Step 4
        def helper(nums, target_sum, subsets, i):
            # Base case
            if i == len(nums) and all(s == target_sum for s in subsets):
                return True
            
            # Recursive case
            for j in range(k):
                if subsets[j] + nums[i] <= target_sum:
                    subsets[j] += nums[i]
                    if helper(nums, target_sum, subsets, i+1):
                        return True
                    subsets[j] -= nums[i]
                    
                # Optimization: if the subset sum is 0, we can early stop
                if subsets[j] == 0:
                    break
                    
            return False
        
        # Step 5
        return helper(nums, subset_sum, subsets, 0)

References:

• LeetCode Problem: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
• Code Repository: https://github.com/vineetjohn/leetcode-solutions/blob/master/solutions/partition_to_k_equal_sum_subsets.py

1