Partition Equal Subset Sum

Problem Statement

You are given an array of positive integers nums.

Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2). Otherwise, return false.

Example 1:

Input: nums = [1, 2, 3, 4]
Output: True

Explanation: The array can be partitioned as [1, 4] and [2, 3].

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Output: False

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 50

You should aim for a solution with O(n * target) time and O(target) space, where n is the length of nums and target is sum(nums) // 2.

Hint 1

Consider the problem as a 0/1 Knapsack problem where you want to find a subset of nums that sums to target.

Hint 2

Dynamic programming can be used to solve this problem efficiently. Create a DP table where dp[i][j] is true if a subset of the first i elements can sum to j.

Hint 3

The base case is dp[0][0] = true, which means an empty set sums to 0.

Solution

Recursion

def can_partition(nums: list[int]) -> bool:
    if sum(nums) % 2:
        return False


    def dfs(i, target):
        if i >= len(nums):
            return target == 0
        if target < 0:
            return False


        return dfs(i + 1, target) or dfs(i + 1, target - nums[i])


    return dfs(0, sum(nums) // 2)

Time complexity: O(2 ^ n) Space complexity: O(n)

Dynamic Programming (Top-Down)

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False


    target = total // 2
    n = len(nums)
    memo = [[-1] * (target + 1) for _ in range(n + 1)]


    def dfs(i, target):
        if target == 0:
            return True
        if i >= n or target < 0:
            return False
        if memo[i][target] != -1:
            return memo[i][target]


        memo[i][target] = (dfs(i + 1, target) or
                           dfs(i + 1, target - nums[i]))
        return memo[i][target]


    return dfs(0, target)

Time complexity: O(n * target) Space complexity: O(n * target)

Dynamic Programming (Bottom-Up)

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False


    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]


    for i in range(n + 1):
        dp[i][0] = True


    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if nums[i - 1] <= j:
                dp[i][j] = (dp[i - 1][j] or
                           dp[i - 1][j - nums[i - 1]])
            else:
                dp[i][j] = dp[i - 1][j]


    return dp[n][target]

Time complexity: O(n * target) Space complexity: O(n * target)

Dynamic Programming (Space Optimized)

def can_partition(nums: list[int]) -> bool:
    if sum(nums) % 2:
        return False


    target = sum(nums) // 2
    dp = [False] * (target + 1)
    next_dp = [False] * (target + 1)


    dp[0] = True
    for i in range(len(nums)):
        for j in range(1, target + 1):
            if j >= nums[i]:
                next_dp[j] = dp[j] or dp[j - nums[i]]
            else:
                next_dp[j] = dp[j]
        dp, next_dp = next_dp, dp


    return dp[target]

Time complexity: O(n * target) Space complexity: O(target)

Dynamic Programming (Hash Set)

def can_partition(nums: list[int]) -> bool:
    if sum(nums) % 2:
        return False


    dp = set()
    dp.add(0)
    target = sum(nums) // 2


    for i in range(len(nums) - 1, -1, -1):
        next_dp = set()
        for t in dp:
            if (t + nums[i]) == target:
                return True
            next_dp.add(t + nums[i])
            next_dp.add(t)
        dp = next_dp
    return False

Time complexity: O(n * target) Space complexity: O(target)

Dynamic Programming (Optimal)

def can_partition(nums: list[int]) -> bool:
    if sum(nums) % 2:
        return False


    target = sum(nums) // 2
    dp = [False] * (target + 1)


    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]


    return dp[target]

Time complexity: O(n * target) Space complexity: O(target)

Dynamic Programming (Bitset)

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False


    target = total // 2
    dp = 1 << 0


    for num in nums:
        dp |= dp << num


    return (dp & (1 << target)) != 0

Time complexity: O(n * target) Space complexity: O(target)