Difference in runtime and memory usage between two near identical functions-CodePudding

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!

CodePudding user response：

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.