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)