698.Partition_to_K_Equal_Sum_Subsets(Medium).md

698. Partition to K Equal Sum Subsets (Medium)

Date and Time: Dec 3, 2024, 23:07 (EST)

Link: https://leetcode.com/problems/partition-to-k-equal-sum-subsets

Question:

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.

Example 1:

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

Output: true

Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

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

Output: false

Constraints:

• 1 <= k <= nums.length <= 16

• 1 <= nums[i] <= 10^4

• The frequency of each element is in the range [1, 4].

Walk-through:

First get the target which is the sum that every subarray want. We can calculate it by sum(nums) / k.

Run Backtrack from the beginning of nums, we use curSum to keep track of current subarray's summation, if curSum == k we decrement k -= 1 and mark all the used elements to be True in visited[], then we run backtrack from the beginning again, but we can't reuse the used elements, so we will find new subarray. We return True, only when k == 0.

There are some tricks to speed up: 1. we check if sum(nums) % k, we can know if this is possible to divide k subarrays. If not, we can return False. 2. we can sort nums in descending order, so the duplicate elements will be next to each other. Then, we check if the previous element is the same as current element, but the previous element has not been used previously, so we know we don't need to use this element either, because they are the same. So, we can skip this element.

Python Solution:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # Use sum(nums) / k to calculate the value for k subsets
        # If sum(nums) / k can't be evenly divided, return False
        # Run backtrack on each digit to form subset, if curSum + nums[i] > target, skip. Otherwise, take this element and run backtrack with this element
        # If curSum == target, we decrement k, run backtrack again from 0th index, mark all the used elements. Reset back to False later.
        # Return True when k == 0

        # TC: O(k * 2^n), SC: O(n)
        # Check if sum(nums) can be evenly divided
        if sum(nums) % k:
            return False
        target = sum(nums) / k
        visited = [False] * len(nums)
        nums.sort(reverse=True)
        def backtr(i, k, curSum):
            # two base cases
            if k == 0:
                return True
            if curSum == target:
                return backtr(0, k-1, 0)
            # Try the rest elements for curSum
            for j in range(i, len(nums)):
                # Skip the element is used or curSum + nums[i] > target
                if visited[j] or curSum + nums[j] > target or (j > 0 and not visited[j-1] and nums[j] == nums[j-1]):
                    continue
                visited[j] = True
                if backtr(j+1, k, curSum + nums[j]):
                    return True
                visited[j] = False
            return False
        return backtr(0, k, 0)

Time Complexity: $O(k * 2^n)$
Space Complexity: $O(n)$