How to Solve Partition Equal Subset Sum
Partition Equal Subset Sum Introduction
Partition Equal Subset Sum Introduction
The Partition Equal Subset Sum asks us to determine if the given array can be split such that the two partition sums are equal. This problem requires careful consideration and checks such as checking if the sum is divisible by two and sorting the array so that we can keep a running current sum until we equal the target sum.
Partition Equal Subset Sum Problem
Partition Equal Subset Sum Problem
Given an array of positive numbers, determine if the array can be split such that the two partition sums are equal.
Example Inputs and Outputs
Example 1
Input: nums = [1,5,11,5]
Output: True
Example 2
Input: nums = [1,2,3,5]
Output: False
Partition Equal Subset Sum Solutions
Partition Equal Subset Sum Solutions
We can solve this problem using the dynamic programming approach. First, we calculate the total sum of the array and check if it is divisible by 2. If not, it is impossible to partition the array equally, so we return false. Next, we set the target sum as half of the total sum and sort the array in ascending order. We initialize a set called sums with an initial value of 0, representing an empty subset. We iterate through each number in the array and for each number, we create a new set called newSums to store the updated sums.
For each sum in the sums set, we add the current number to it and check if the new sum is equal to the target sum. If it is, we have found a valid partition, so we return true. If the new sum is less than the target sum, we add it to the newSums set. After iterating through all numbers, we update the sums set with the contents of the newSums set. If we cannot find a valid partition after iterating through all numbers, we return false. Our approach considers all possible combinations of numbers to determine if a valid partition exists.
def canPartition(nums):
total_sum = sum(nums) # Calculate the total sum of the array
if total_sum % 2 != 0: # If the sum is not divisible by 2, return False
return False
target_sum = total_sum // 2 # Set the target sum as half of the total sum
nums.sort() # Sort the array in ascending order
sums = set([0]) # Initialize a set to store the unique sums, starting with 0
for num in nums:
if num > target_sum: # If the current number is greater than the target sum, break the loop
break
new_sums = set() # Create a new set to store updated sums
for val in sums:
new_sum = val + num
if new_sum == target_sum: # If the new sum is equal to the target sum, return True
return True
elif new_sum < target_sum: # If the new sum is less than the target sum, add it to the new_sums set
new_sums.add(new_sum)
sums.update(new_sums) # Update the sums set with the new_sums set
return False # If a valid partition is not found, return False
# Driver code and test case
nums = [1, 5, 11, 5]
result = canPartition(nums)
print(result) # Expected output: True
1def canPartition(nums):
2 total_sum = sum(nums) # Calculate the total sum of the array
3
4 if total_sum % 2 != 0: # If the sum is not divisible by 2, return False
5 return False
6
7 target_sum = total_sum // 2 # Set the target sum as half of the total sum
8
9 nums.sort() # Sort the array in ascending order
10
11 sums = set([0]) # Initialize a set to store the unique sums, starting with 0
12
13 for num in nums:
14 if num > target_sum: # If the current number is greater than the target sum, break the loop
15 break
16
17 new_sums = set() # Create a new set to store updated sums
18
19 for val in sums:
20 new_sum = val + num
21
22 if new_sum == target_sum: # If the new sum is equal to the target sum, return True
23 return True
24 elif new_sum < target_sum: # If the new sum is less than the target sum, add it to the new_sums set
25 new_sums.add(new_sum)
26
27 sums.update(new_sums) # Update the sums set with the new_sums set
28
29 return False # If a valid partition is not found, return False
30
31
32# Driver code and test case
33nums = [1, 5, 11, 5]
34result = canPartition(nums)
35print(result) # Expected output: True
36Time/Space Complexity Analysis
- Time Complexity: O(n * sum), where n is the length of the input array. This is because for each number in the array, we iterate over the current set of sums, which has a maximum size of sum. Therefore, the overall time complexity is proportional to the number of iterations performed, which depends on the size of the array and the sum.
- Space Complexity: O(sum), as we use sets to store the unique sums.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
