## # 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:
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: