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)