Python solution with detailed explanation


  • 1
    G

    Solution

    Partition Equal Subset Sum https://leetcode.com/problems/partition-equal-subset-sum/

    Algorithm

    • If the sum of all elements is odd, then you cannot have 2 subsets with equal sum. So test this and return False.
    • If the sum is even, then the problem produces to find a subset which is equal to a target sum.
    • is_subset(i, target) = Can we form target using array[i,...N-1]?
    • You can include nums[i] or exclude nums[i] and reduce the problem to the nums array starting from i+1.
    • is_subset(i, target) = is_subset(i+1, target) or is_subset(i+1, target-nums[i])
    from collections import defaultdict
    class Solution(object):
        def helper(self, i, array, target, cache):
            if target == 0:
                return True
            elif target < 0 or i == len(array):
                return False
            else:
                if i in cache and target in cache[i]:
                    return cache[i][target]
                else:
                    cache[i][target] = self.helper(i+1, array, target, cache)
                    if target-array[i] >= 0:
                        cache[i][target] = cache[i][target] or self.helper(i+1, array, target-array[i], cache)
                    return cache[i][target]
    
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            total = sum(nums)
            if total & 1:
                return False
            else:
                target = total // 2
            return self.helper(0, nums, target, defaultdict(dict))
    

Log in to reply
 

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