Partition Equal Subset Sum
Given an array of integers, determine if it can be partitioned into two subsets such that the sum of the elements in each subset is equal.
A partition is considered valid if it divides the array into two subsets where both subsets have the same sum.
Examples
Input: [2, 4, 11, 5] Output: True Explanation: The array can be partitioned into two subsets [2, 4, 5] and [11] with equal sum. Input: [2, 7, 3, 1] Output: False Explanation: The array cannot be partitioned into two subsets with equal sums.
Our solution processes the input array by first calculating the total sum of the array elements and then determining if it can be partitioned into two subsets with equal sums. The core idea is based on dynamic programming.
-
Calculate Total Sum: We start by computing the total sum of the array elements. If the total sum is odd, it is immediately impossible to partition it into two subsets with equal sums, so we return
false. -
Define Target Sum: If the total sum is even, we calculate the target sum for each subset, which is half of the total sum.
-
Dynamic Programming Array: We use a boolean array
dpwheredp[i]indicates whether a subset sum ofiis achievable. We initializedp[0]totruebecause a subset sum of0is always achievable (by taking no elements). -
Iterate Through the Array: For each number in the array, we update the
dparray in reverse order (fromtargetdown to the current number). This reverse iteration ensures that each number is only used once in the current update.- If a subset sum
i - numwas achievable, then adding the current numbernummakesdp[i]achievable. We updatedp[i]totrueaccordingly.
- If a subset sum
-
Check Final Result: After processing all numbers, if
dp[target]istrue, it means there is a subset with the required sum equal totarget, indicating that the array can be partitioned into two subsets with equal sums. Otherwise, we returnfalse.
The use of a boolean array ensures that we efficiently keep track of achievable subset sums.
from typing import List
def can_partition(nums: List[int]) -> bool:
total_sum = sum(nums)
# If the total sum is odd, it's not possible to partition it into two equal subsets
if total_sum % 2 != 0:
return False
target = total_sum // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for i in range(target, num - 1, -1):
dp[i] = dp[i] or dp[i - num]
return dp[target]Time Complexity: The solution has a time complexity of O(n * target), where n is the number of elements in the array and target is half of the total sum. This is because we iterate through the array and update the dp array for each element.
Space Complexity: The solution uses O(target) space for the dp array, where target is half of the total sum. This space is needed to store the achievable subset sums.
This could be done using two-pointer approach assuming array is sorted: left and right pointers. We need track two sums (left and right) as we move pointers. For moving pointers we will move left to right by 1 (increment) when right sum is greater. We will move right pointer to left by 1 (decrement) when left sum is greater. at some point we will either get the sum same and that's when we exit from the loop. 0-left will be one array and right-(n-1) will be another array.
We are not going to move the elements assuming they are already sorted. Time complexity = O(N) Space Complexity = O(1) - for the traversal
O(N) - for the result