LC 0416 [M] Partition Equal Subset Sum - ALawliet/algorithms GitHub Wiki

The above solution times out because we were performing repeated calculations over and over unnecessarily. The result for a given parameters sum, i (can we achieve subset sum = sum starting from i index?) will always be the same. So once we have calculated it, we don't need to repeat the whole calculation again when it is called from another recursive branch. Instead we can save the result for this state and return it whenever we called again.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        div, mod = divmod(sum(nums), 2)
        
        if mod % 2:
            return False
        
        dp = set()
        dp.add(0)
        target = div
        
        for i in range(len(nums) - 1, -1, -1):
            nextDP = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
            
        return target in dp

class Solution:
    def canPartition(self, nums) -> bool:
        S = sum(nums) # total sum
        if S % 2 != 0: # total sum can't be halved equally
            return False
        S = S // 2 # half sum for equal subset

        @cache
        def helper(s, i): # sum so far, current index
            if s == S: # sum so far is equal to the half sum
                return True
            if i == len(nums):
                return False
            return helper(s, i + 1) or helper(s + nums[i], i + 1) # exclude or include

        return helper(0, 0)