# 698. Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's 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's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

# Solution

Approach 1: backtracking. Have k buckets of nums, each adds up to sum(nums)/k. For each num, try to put it into a bucket. Time: O(k^N).

Approach 2: backtracking. For each bucket, handpick all values that can fit into it from the array, until k-1 buckets are filled up. TIme: O(k * 2^N).

# Code (Python)

Approach 1:

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # idea: backtracking. Have k buckets of nums, each adds up to sum(nums)/k. For each num, try to put it into a bucket.
        # O(k^N)
        bucket_sum = sum(nums) / k
        if int(bucket_sum) != bucket_sum or max(nums) > bucket_sum:
            return False
        buckets = [0 for _ in range(k)]
        nums.sort(reverse=True) # trick: try fit in the bigger chunks first
        return self._can_partition(0, buckets, nums, bucket_sum)
    
    def _can_partition(self, start, buckets, nums, target):
        if all(map(lambda val: val == target, buckets)):
            return True
        used_bucket_sums = set()
        for i, bucket in enumerate(buckets):
            if bucket + nums[start] <= target and bucket not in used_bucket_sums:
                used_bucket_sums.add(bucket)
                buckets[i] += nums[start]
                if self._can_partition(start + 1, buckets, nums, target):
                    return True
                buckets[i] -= nums[start]
        return False

Approach 2:

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # idea: backtracking. For each bucket, handpick all values that can fit into it from the array, until k-1 buckets are filled up.
        # O(k * 2^N)
        bucket_sum = sum(nums) / k
        if int(bucket_sum) != bucket_sum or max(nums) > bucket_sum:
            return False
        self.bucket_target = bucket_sum
        return self._can_do(0, bucket_sum, k, set(), nums)
    
    def _can_do(self, start, sum_remaining, buckets_remaining, included_indices, nums):
        if sum_remaining == 0:
            # stop when we can put k-1 buckets together (the rest unincluded nums can fill up the last bucket)
            if buckets_remaining == 1:
                return True
            # start filling up another bucket
            else:
                return self._can_do(0, self.bucket_target, buckets_remaining - 1, included_indices, nums) # pick numbers from the beginning
        for i in range(start, len(nums)):
            if i not in included_indices and nums[i] <= sum_remaining:
                included_indices.add(i)
                if self._can_do(i + 1, sum_remaining - nums[i], buckets_remaining, included_indices, nums): # rest of the array because it's the same bucket
                    return True
                included_indices.remove(i)
        return False

# Code (C++)

Approach 1:

Approach 2: