AC Python solution, dfs


  • -1

    The regular dfs solution will TLE. So I sort the array first, and search from thwo ends. This can optimize the time consuming a little bit.

    class Solution(object):
        def canPartitionKSubsets(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            if len(nums) < k or sum(nums) % k != 0 :
                return False
            sub_sum = sum(nums) / k
            if any(num > sub_sum for num in nums):
                return False
            nums.sort()
            return self.dfs(sub_sum,nums[-1], nums[: -1])
        
        def dfs(self, sub_sum, cur_sum, nums):
            if cur_sum == sub_sum:
                
                if not nums:
                    return True
                return self.dfs(sub_sum, nums[-1], nums[: -1])
            size = len(nums)
            for index in xrange(size):
                tmp = nums[index]
                if nums[index] + cur_sum <= sub_sum:
                    nums[index], nums[-1] = nums[-1], nums[index]
                    nums.pop()
                    if self.dfs(sub_sum, cur_sum + tmp, nums):
                        return True
                    nums.append(tmp)
                    nums[index], nums[-1] = nums[-1], nums[index]
            return False
    

  • 0
    H

    if any(num > sub_sum for num in nums): return False
    Elements in nums are always positve?


Log in to reply
 

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