Python solution with detailed explanation

  • 0

    Partition to K Equal Sum Subsets

    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
                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
            if nums[0] > target: raise
            nums = deque(nums)
            while nums and nums[0] == target:
                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
                (target, nums, k) = self.optimize_input(nums, k)
                return self.helper(i=0, nums=nums, bins=[0]*k, target=target)
                return False

  • 0
    This post is deleted!

Log in to reply

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