Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
The description was taken from https://leetcode.com/problems/partition-equal-subset-sum/.
#O(M*N) Time, O(M*N) Spaceclass Solution: def canPartition(self, nums: List[int]) -> bool: total_sum = sum(nums) if total_sum % 2 != 0: return False subset_sum = total_sum // 2 dp = [[False] * (subset_sum+1) for rows in range(len(nums)+1)] dp[0][0] = True for i in range(1,len(nums)+1): current = nums[i-1] for j in range(0, subset_sum+1): if j < current: dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] or dp[i-1][j-current] return dp[-1][-1]If we are looking for specific subsequences, not sublists, that follows a specific constraint, that is typically an indication that Dynamic Programming can be applied.
We can build a two-dimensional array that we will use as a lookup table. We will split the input array into subproblems of length one, two, three, etc. Since we are trying to partition two equal sum subsets, our overall question is to see if we could get a subset that sums to half the total sum of the input array because the remaining subset would sum to the other half.
Within each subproblem, we will be asking a couple of questions, "Have we summed to this current subset subproblem sum before without including the element at the current index?", or "Can we sum to this current subset subproblem sum now by including the element at the current index?". By incrementally building up a table of our sub answers, we will be able to yield the final, overall answer.
Let's expand on this solution.
We will start by taking the total sum of the array.
If the total sum isn't an even number, then there is no way that we would be able to sum to it through two even subsets, so we would return false.
Otherwise, we will create a subset_sum variable that we will aim to sum to. This value will be half of the total sum.
total_sum = sum(nums) if total_sum % 2 != 0: return False subset_sum = total_sum // 2
We will create our dp array that will hold the answers for each subproblem that we will refer to.
The base case of dp[0][0] will be true, because we can sum to zero with a subset of length zero, so this case would always be true.
dp = [[False] * (subset_sum+1) for rows in range(len(nums)+1)]
The code above basically translates to "We want an array of False in the length of the subset-sum plus one and we will want rows of that array in the length equal to of the input array plus one."
We will then create our "expansion" loop, with the iterator i, and this loop will traverse up to the last character of the input array. This is the loop that we will use to incrementally expand the range of our subproblem. During each of these iterations, we will take a current number from the input array.
for i in range(1,len(nums)+1): current = nums[i-1]
Next, we will create our "subproblem partition" loop with the iterator j and this loop will only focus on the range between the first character of the string to the character i is at.
This loop is where we break the overall problem into subproblems, notice that the range of the traversals for this loop will go from index zero to one, index zero to two, index zero to three, etc.
for j in range(0, subset_sum+1):
Let's draw out what a complete dp array would look like for the input of [1,2,3,4].
| Subproblem Answered | Current (i) |
Sum ( j) |
|||||
| 0 | 1 | 2 | 3 | 4 | 5 | ||
| {} | 0 | True | False | False | False | False | False |
| {1} | 1 | True | True | False | False | False | False |
| {1,2} | 2 | True | True | True | True | False | False |
| {1,2,3} | 3 | True | True | True | True | True | True |
| {1,2,3,4] | 4 | True | True | True | True | True | True |
Now we will start asking our subproblems questions.
If the subproblem sum is less than the current element, then we will see if we can sum to the given subproblem without the current element because we can't shove a larger number into a smaller sum. That is like if we were trying to sum to two and our current number is seven, we would want to see if we summed any previous elements to two instead.
To figure out the answer to this subproblem, we will go to the previously answered subproblem in the dp array that is directly above the current spot, that is where we asked the same subproblem sum question, but for a previous, current number.
| Subproblem Answered | Current Number (i) |
Current Sum ( j) |
|||||
| 0 | 1 | 2 | 3 | 4 | 5 | ||
| {} | 0 | True | False | False | False | False | False |
| {1} | 1 | True | True | False | False | False | False |
| {1,2} | 2 | True | True | True | True | False | False |
| {1,2,3} | 3 | True | True | True | True | True | True |
| {1,2,3,4] | 4 | True | True | True | True | True | True |
In the table above, our current number is two and we are trying to sum to one. We don't want to try to sum to a smaller number than our current number, so we will check if we can sum to one without the two. We will move one element directly above and sure enough, we can sum to one by seeing that we had summed to one in a previous iteration when the current number was one.
if j < current: dp[i][j] = dp[i-1][j]
Otherwise, if our current subproblem sum is greater than or equal to the current number, we will still check if we could sum to the subproblem's sum without the current number as we did previously, but we will also see if we could sum to it including the given number by referring to the complement's previous subproblem answer.
| Subproblem Answered | Current Number (i) |
Current Sum ( j) |
|||||
| 0 | 1 | 2 | 3 | 4 | 5 | ||
| {} | 0 | True | False | False | False | False | False |
| {1} | 1 | True | True | False | False | False | False |
| {1,2} | 2 | True | True | True | True | False | False |
| {1,2,3} | 3 | True | True | True | True | True | True |
| {1,2,3,4] | 4 | True | True | True | True | True | True |
In the table above our current number is two and we are trying to sum to three. Here we utilize the formula x+y=z.
x+2=3,
x=1.
We see that one is set to true. This means that we can use our current number, two, and our previous current number, one, and get a sum of three.
1+2=3.
We will mark the current subproblem answer as true.
else: dp[i][j] = dp[i-1][j] or dp[i-1][j-current]
Once we are finished building up our table of subproblem answers, the final, overall answer will be in the last index of the array. We will just need to return its value to get our output.
return dp[-1][-1]
Since we only need to hold the answer to the previous iteration to see if we can sum to a given value without the current number, we actually only need a one-dimensional array.
We will be asking the same subproblem questions and will build up the dp array in the same fashion.
What differs between this solution and the previous one is we will want to traverse subproblem partitions backward.
The issue lies in the first few numbers if we were to scan from left to right because zero and two share the same complement of one.
x+0=1, x=1,
x+1=2, x=1.
This means if our current number is one and wanted to see if we could sum to two, we would see that we had the complement set to true in our dp array since it was set it previously for zero, and we'd think we could make a sum of two if we only had one and zero, then we would get a false positive because 1+0 != 2.
#O(M*N) Time, O(M) Spaceclass Solution: def canPartition(self, nums: List[int]) -> bool: total_sum = sum(nums) if total_sum % 2 != 0: return False subset_sum = total_sum // 2 dp = [True] + [False] * subset_sum for current in nums: for j in range(subset_sum, current-1, -1): dp[j] = dp[j] or dp[j-current] return dp[-1]