# Python solution with detailed explanation

• 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[0] > target: raise
nums = deque(nums)
while nums and nums[0] == 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=[0]*k, target=target)
except:
return False
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.