Partition Equal Subset Sum

Problem Id: 416 Difficulty: Medium


Intuition

Solution


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2 == 1:
            return False
        target = target // 2

        visited = {0}

        for num in nums:
            for prev in list(visited):
                if prev + num > target:
                    continue
                if prev + num == target:
                    return True
                visited.add(prev + num)
        return False