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