Untitled

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # if valid partition, sum of one subset = sum(nums) / 2
        # find a valid partition by backtracking valid combinations
        if sum(nums) % 2 == 1:
            return False

        target = sum(nums) / 2

        def backtrack(currSum, start):
            if currSum == target:
                return True

            if currSum > target or start >= len(nums):
                return False

            return backtrack(currSum + nums[start], start+1) or backtrack(currSum, start+1)
        
        return backtrack(0, 0)