We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition to K Equal Sum Subsets

Difficulty: Medium

Problem Description

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.

Key Insights

  • The total sum of the array must be divisible by k to partition it into k equal subsets.
  • Each subset must sum to total_sum / k.
  • The problem can be approached using backtracking to explore potential partitions.
  • Efficient pruning can be implemented to skip impossible configurations early.

Space and Time Complexity

Time Complexity: O(2^n) where n is the number of elements in nums, due to potential subsets explored. Space Complexity: O(n) for recursion stack space used during the backtracking.

Solution

The solution employs a backtracking approach to recursively try to fill subsets with the target sum. We use a boolean array to keep track of which numbers have been used in the current partitioning. The algorithm checks if we can form subsets by iterating through the numbers and attempting to build up to the required sum. If we can achieve the required number of subsets with the target sum, we return true; otherwise, we backtrack.

Code Solutions

def canPartitionKSubsets(nums, k):
    total_sum = sum(nums)
    if total_sum % k != 0:
        return False
    
    target = total_sum // k
    nums.sort(reverse=True)  # Sort in descending order to optimize
    used = [False] * len(nums)

    def backtrack(start_index, current_sum, count):
        if count == k - 1:  # All other subsets are filled
            return True
        if current_sum == target:
            return backtrack(0, 0, count + 1)  # Start a new subset
        for i in range(start_index, len(nums)):
            if not used[i] and current_sum + nums[i] <= target:
                used[i] = True
                if backtrack(i + 1, current_sum + nums[i], count):
                    return True
                used[i] = False  # Backtrack
        return False

    return backtrack(0, 0, 0)
← Back to All Questions