partition_equal_subset_sums.py

from functools import lru_cache

class Solution:
    
    def subset_sum(self, target: int, nums: List[int]):
        visited = set()

        @lru_cache(None)
        def dfs(target_sum):
            # print(f"target_sum = {target_sum} nums = {nums}")
            if target_sum == 0:
                return True
            elif target_sum < 0:
                return False
            else:
                for i, num in enumerate(nums):
                    if i in visited:
                        continue
                    visited.add(i)
                    if dfs(target_sum - num):
                        return True
                    visited.remove(i)
                return False
        
        return dfs(target)

    def canPartition(self, nums: List[int]) -> bool:
        nums_sum = sum(nums)
        return self.subset_sum(nums_sum // 2, nums) if nums_sum % 2 == 0 else False