Simple Backtracking with Memoization, Python.


  • 0
    Y
        def canPartitionKSubsets(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            self.k = k
            self.memo = {}
            target_sum = 1.0 * sum(nums)/k
            if abs(int(target_sum) - target_sum) != 0:
                return False
            nums = sorted(nums)[::-1] # can_use
            num_groups = 0
            cur_sum = 0
            return self.dfs(nums, num_groups, target_sum, cur_sum)
            
        def dfs(self, num_list, num_groups, target_sum, cur_sum):
            key = str(num_groups) + ":" + str(cur_sum) + ":" + str(num_list)
            if key in self.memo:
                return self.memo[key]
            
            if num_groups == self.k:
                self.memo[key] = True
                return True
            if cur_sum > target_sum:
                self.memo[key] = False
                return False
            for index, num in enumerate(num_list):
                num_list[index] = float('inf')
                if num + cur_sum == target_sum:
                    if self.dfs(num_list, num_groups+1, target_sum, 0):
                        num_list[index] = num
                        self.memo[key] = True
                        return True
                else:
                    if self.dfs(num_list, num_groups, target_sum, num + cur_sum):
                        num_list[index] = num
                        self.memo[key] = True
                        return True
                num_list[index] = num
            self.memo[key] = False
            return False
    

Log in to reply
 

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