Partition Equal Subset Sum

The problem description can be found in LeetCode.

Approach

The problem asks us to partition the input array in two subsets, which sum up to the same value:

nums = [1, 1, 1]

It is clear that, in the case above, these two subsets do not exist. In particular, if the sum of the list is an odd number, for sure there is no solution for the problem.

So, since we know that our target is an even number, the problem can be seen as looking for a single subset, which sums up to target // 2 (// is the integer division in Python).

We then have the choice of either selecting an element or not.

Solution

from typing import Dict, List, Tuple


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        def dfs(i: int, target: int, memo: Dict[Tuple[int, int], bool]) -> bool:
            if (i, target) in memo:
                return memo[(i, target)]
            if target == 0:
                return True
            if target < 0 or i >= len(nums):
                return False

            with_curr_val = dfs(i + 1, target - nums[i], memo)
            without_curr_val = dfs(i + 1, target, memo)
            ans = with_curr_val or without_curr_val
            memo[(i, target)] = ans

            return ans

        nums_sum = sum(nums)
        if nums_sum % 2 != 0:
            return False

        return dfs(0, nums_sum // 2, {})

Complexity

• Time: $O(nt)$
• Space: $O(nt)$

Where $n$ is the size of the nums list and $t=\frac{target}{2}$.