Partition to K Equal Sum Subsets https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
Simulate distributing N balls in K bins with bin capacity
- Compute the capacity or target sum for each bin. Do optimizations on the input - return False if we have any number greater than target in the input. Any number equal to target can be placed in a bin and the required number of bins can be reduced. Additionally, sort the input in descending order which will let us fail early or fill early.
- Now write recursive code to simulate filling bins. Once we place a num[i] in bin j, we call the subproblem with (i+1:len(num)-1). If we find a solution, we return True. Otherwise, if bin[j] is left with 0, we are moving towards an invalid solution and we can eliminate the search branches from j+1 to k-1. This is a powerful optmization.
- Time complexity is O(k^(N-k)) - we can atmost N-k levels of the recursion tree and in each level we do order k work. Why N-k levels - every bin must have atleast one element.
- Space complexity is O(N) or depth of the recursion tree.
class Solution: def helper(self, i, nums, bins, target): if i == len(nums): return True else: for k in range(len(bins)): if bins[k]+nums[i] <= target: bins[k] = bins[k]+nums[i] if self.helper(i+1, nums, bins, target): return True bins[k] = bins[k]-nums[i] if bins[k] == 0: break # Most powerful optimization return False def optimize_input(self, nums, k): from collections import deque target = sum(nums)//k nums.sort(reverse=True) if nums > target: raise nums = deque(nums) while nums and nums == target: nums.popleft() k = k-1 if len(nums) < k: raise return (target, nums, k) def canPartitionKSubsets(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ try: (target, nums, k) = self.optimize_input(nums, k) return self.helper(i=0, nums=nums, bins=*k, target=target) except: return False