Why is Leetcode's Solution 10x faster than mine?

Viewed 76

I thought I had the optimal DP solution for Leetcode 416 but my solution was 10x slower than leetcode's. Why is that?

My Code:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = {}
        def backtracking(index, subset_total):
            if index == (len(nums) - 1):
                if subset_total == target:
                    return True
                else:
                    return False
            if (index, subset_total) in dp:
                return dp[(index, subset_total)]
            dp[(index, subset_total)] = backtracking(index+1, subset_total) or backtracking(index+1, subset_total + nums[index])
            return dp[(index, subset_total)]
        return backtracking(0,0)

Leetcode's Solution:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        @lru_cache(maxsize=None)
        def dfs(nums: Tuple[int], n: int, subset_sum: int) -> bool:
            # Base cases
            if subset_sum == 0:
                return True
            if n == 0 or subset_sum < 0:
                return False
            result = (dfs(nums, n - 1, subset_sum - nums[n - 1])
                    or dfs(nums, n - 1, subset_sum))
            return result

        # find sum of array elements
        total_sum = sum(nums)

        # if total_sum is odd, it cannot be partitioned into equal sum subsets
        if total_sum % 2 != 0:
            return False

        subset_sum = total_sum // 2
        n = len(nums)
        return dfs(tuple(nums), n - 1, subset_sum)
0 Answers
Related