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
Recommended Time and Space Complexity
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)