Difference in runtime and memory usage between two near identical functions

user_14836806 0
Viewed 54

I've been working on my data structure/algorithm skills, and I encountered the following question (LeetCode 416. Partition Equal Subset Sum):

"Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal."

EX:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

My solution is as follows:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        if sum(nums) % 2 == 1:
            return False
        memo = {}
        
        def check_all(i, target):
            if (i, target) in memo:
                return memo[(i, target)]
            if target == 0:
                return True
            if i == len(nums) and target != 0:
                return False
            
            if nums[i] > target:
                not_included = check_all(i+1, target)
                memo[(i, target)] = not_included
                return not_included
            
            memo[(i, target)] = check_all(i+1, target) or check_all(i+1, target-nums[i])
            return memo[(i, target)]
        
        return check_all(0, sum(nums)//2)

This solution is accepted with a runtime of 5276 ms and memory usage of 469 MB. After submitting my solution, I looked around at other solutions, and I found the following code:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2 != 0:
            return False
        
        return self.helper({} ,nums, target//2, 0)
        
    def helper(self, dp, nums, target, i):
    # Using memoization, if we have already computed result for given i and target, we return that
        if (i,target) in dp:
            return dp[(i,target)]
            
        # if target becomes 0 that means we found a subset that has sum == target
        if target == 0:
            return True
        # if we have checked all numbers in nums but we can't find a subset whose sum is equal to target, we return False
        if i == len(nums) and target != 0:
            return False
        
        #checking wether to include curr num or not
        if nums[i] > target:
            dp[(i,target)] = self.helper(dp,nums, target, i+1)
            return dp[(i,target)]
        
        # if either selecting curr num returns True or not selcting it returns True we return True
        dp[(i,target)] = self.helper(dp,nums,target-nums[i],i+1) or self.helper(dp,nums,target,i+1)
        return dp[(i,target)]

This second solution is accepted with a runtime of 1922 ms and memory usage of 140 MB. I cannot for the life of me figure out why the second solution is so much more efficient than the first. I'd appreciate any insight that someone could provide!

data-structures algorithm python
1 Answers

The main difference lies here:

# your approach
memo[(i, target)] = check_all(i+1, target) or check_all(i+1, target-nums[i])

# more efficient approach
dp[(i,target)] = self.helper(dp,nums,target-nums[i],i+1) or self.helper(dp,nums,target,i+1)

In the second approach, the first recursive call (self.helper(dp,nums,target-nums[i],i+1)) reduces the search space (since target is decremented and i is incremented), and goes to the second recursive call (which only increments i) only if the first call doesn't find a solution.

In your approach, you use the "inefficient" recursive call first, which searches in a larger space than required. This why your approach takes more time/memory.

user_93507200
Related