Partition Equal Subset Sum - Leetcode 416 - Python

Hey everyone, welcome back and let's write some more neat code today. So today let's solve Partition Equal Subset Sum. So this is a pretty interesting problem. So we're given a non-empty array of nums containing only positive integers. We want to know if the array can be partitioned into two different subsets such that the sum of each of the subsets is exactly equal. Notice how that's basically saying if we can take one subset of the array which is going to equal half of the sum of the entire array, right? Because if we partition it into two equal halves, right? Let's say the total sum was 22. If we partitioned it into equal halves, then each of the halves would be exactly 11, right? AKA one of the partitions is going to be half that of the total sum. So for example, in this problem the sum is exactly 22. So we want to know can we get a partition or can we get a subset of this array? Basically, we can choose any of the values and can we get a subset such that it sums up to 11. In this case, the answer is yes, it's true because we can take, you know, the single 11. That sums up to 11, right? And obviously, if there's one way to get half of the sum of the total array, then the remaining elements are going to basically equal 11 as well, right? So you can see that 1 + 5 + uh another 5 is going to be equal to 11, right? Basically, these are the two partitions. So as with many problems, let's just try to figure out what the brute force solution would be. So basically, let's start at the first element, right? And for every single element that we visit, we have two choices, right? We can either include this in our sum or we can not include it in our sum. And we want to basically determine every single sum that we can make with any single subset from this given array. And we want to know does that sum ever equal 11? Because 11 is our target, right? If we sum this up, divide it by two, we get 11. So we want to know if that's possible. So let's brute force it, right? So the first choice, we can either choose a one or choose nothing, right? Basically, skipping that. So either our sum will be one or our sum will be zero because initially, our sum is zero. So the next value is five, right? So basically, for each of these uh paths, we can choose five or not choose five. If we do choose five here, we'll get a six. If we don't, we'll stay at one. Otherwise, on this path, if we choose the five, we'll get a five because we started at zero. So if we skip the five, we'll stay at zero. Next, we get a we get an 11. So basically, continuing that, right? So I don't know if I'm going to have enough room for this. Okay, now 11 + 6 is going to give us 17 on this path. Clearly, we went over, so we would probably not want to continue down this path. But over here, if we skip the 11, we'll get a six still. If we take 11 here, we're going to get 12. If we skip it, we'll get one. And etc. etc. We'll get 16 here, skip, we'll get five. If we take 11 here, we'll get 11, skip, get zero. But clearly, we found our target that we were looking for. We we don't really have to continue anymore, right? So basically, we can skip this last element. We found our target. We're going to return true and we're going to go back up. So as you can tell, since every level of our decision tree, we're having two choices, right? And what's the height of this decision tree going to be? Basically, for every single element, right? We're going to have a decision. So let's say the input size of the array is n. So basically, our time complexity is going to be 2 to the power of n if we do a brute force method. So let's go back to the first step. Basically, the first element that we were at and let's see if there's any repeated work that we can cut down on. So initially, our index or our I pointer is at the first element, right? So basically, we're at the beginning of the array. We can go down the entire array. We can choose any elements from here. But and we want to know can we sum up to the target 11? Now, once we take our two paths, right? We're basically going to say I is now going to be shifted to the next element five, right? And we had two choices. We could have either chosen the one or we could have skipped the one. But clearly, now we have a new subproblem. We already have a one. So from the perspective of this decision, we're not looking for a target of 11 anymore, right? We're looking for a target of 10. We're looking for a target of 10. And not only that, but our initially, our I pointer was here, meaning we could have we could have done the entire array. But now our I pointer is over here. So we're not even looking at the entire array anymore. We're looking at a subarray. Basically, the remaining elements of the array minus this first one. So if we were to cache this, our new subproblem would be target of 10 that we're trying to solve. And I is not at zero anymore. Index is at one. Similarly, over here we can see since we're at zero, the target is still 11, right? We are trying to sum up all the way to 11. But the index that we're starting at in this case as well is one now, right? Because we basically said we were skipping this element down this path, right? So now we want to know is there a way that we can sum up to 11 basically just from this subarray, right? And every time we made a decision, we would continue to update these values, target and I, right? So as you can see, what are the dimensions of our cache going to be? If these are the two variables of our cache, what are the dimensions going to be? Well, clearly clearly I could be any value in the input array. So the dimensions of our cache are going to be n where basically n is the size of the input array, right? Because I could be at any value from zero to n minus one. And what about the target? Well, the target is basically the sum of the entire array divided by two, right? So basically, sum of nums divided by two. Or, you know, constants usually don't matter in time complexity. So basically, this is going to be the big O time complexity. Now, this is technically better than 2 to the power of n because they do give us a pretty good limitation. Like the values in this input array are usually going to be, I think, less than or equal to 200. Now, if they were really big, like if this could have been a million, clearly that would not be very efficient because our sum could have potentially been super large. But this is basically the best way that we can optimize it. So basically, if we did a depth-first search solution with a cache, like a backtracking solution with a cache, this would be the time complexity and this would also be the memory complexity because this would be the dimensions of our cache. But it's actually possible to improve the memory complexity a little bit with dynamic programming. And the time complexity is mainly going to stay the same as this, but the overall memory complexity can be improved. And let me show you why that's the case. So suppose we were starting at this first value, right? And let's say we already knew all the possible sums that any given subset from the remainder of this array. Like basically, what we could do is say for every single one of those sums, we we would add one to it, right? So for every T, let's just call it T for now, in that subarray, we're going to be basically be checking two things, right? Either if T is equal to target, right? Like some possible sum from this subarray totaled up to the target, then we would return true, right? Every possible sum that we could create from any subset in this subarray. And if it basically, that that's what T would be. And if that T happened to be equal to the target, target 11, then we would return true, right? Or if we took every single sum we could create from the subarray and added one to it, basically one because that's the only value left over here, right? 1 + T equal to target. If that was also equal to 11, then we would return true as well, right? Basically, this is the recurrence relation that I'm trying to show you. And so this is basically the idea we're going to use for the bottom-up solution. So instead of starting here, we're going to work our way backwards. So we're going to start here. So and this is very simple, right? So how many possible sums could we create from this subarray? Well, there's only one value here, right? We either take it or we don't. So the amount of sums we can create is going to be zero or five. And what I'm going to do is I'm going to be storing these values in a set. So let's say this is our set. So so far we have zero and five. Next, what I'm going to do is I'm going to I'm going to go to 11, right? We're going to work our way backwards. I'm going to start at 11 and I'm going to iterate through every single one of these and I'm basically going to add 11 to them, right? So for zero, let's add 11 to it. That's going to be 11. I'm going to add that to our set. Let's Let's look at five. That's going to be 11. I'm going to add that. 11 + 5 is 16. I'm going to add that to our set, right? Clearly, we can see we already found the target value, so we could return. But let's just keep going to see all the possible targets we could create with this input array. So we we were done visiting 11. Now let's go to five, right? So basically, we're going to iterate through every single one of these, add five to them, and then see if that's a new value. If it's already a value that exists, then we wouldn't do anything. Like in this case, we can see see 5 + 0 is just going to be five, right? So I'm not going to add a second five to this because we already have a five. This is a set. It's going to want only unique values. So we're not going to end up adding a second five. But if we add 5 + 5, that's going to be a 10. If we add 5 + 11, that's going to be a 16. We already have a 16. If we add 5 + 16, that's going to be 21. And basically, I'm going to do the exact same thing with one. So, you know, we would add a one here. We'd add a six. 5 + 1 is 6. 1 + 11 is 12. 1 + 16 is 17. And 1 + 10 is 11. We already have a 11. 1 + 21 is 22. So basically, this is the entire list of sums we could possibly create from our given input array. As long as this uh set contains 11, we return true. If it doesn't contain 11, that means it's impossible to sum up to this target, so we would return false. Now, I think in practice, the size of the set is probably going to be about the same size as the cache that we would use in the memoization uh technique, but technically, the size of this this cache is going to be limited to the size of the target, which is basically uh limited by the sum of the nums input array. So, this is going to be the memory complexity in this case. Technically, the time complexity is going to be the same, but I think this this solution is definitely easier to code. It's just a little bit tricky to actually arrive to this solution. I think going through the brute force to the caching to the dynamic programming solution is the best thought process to arrive to this optimal solution. So, now, let's jump into the code. So, one thing I didn't mention is that if the sum of our input array is odd, then it's obviously going to be impossible to partition it into an equal half, right? So, basically, if the sum of this modded by two is one, then we're going to return false. Also, I'm going to have a DP set, as I mentioned, because this is going to be the most optimal solution. To the DP set, I'm just going to add a base case of zero. Basically, we're guaranteed that we can add up to a sum of zero, right? If we just don't choose any elements from the input array nums, and the target that we're trying to sum up to is, of course, the sum of nums divided by two. So, with that being said, let's iterate through every single value in nums in reverse order. You could do it in regular order, but I'm just going to do reverse order because I'm used to it, so. So, we're going to go through every target or every total value that's already in our DP set for every T in DP, and what we want to do is to DP add a value, right? We basically want to add T plus nums of I, right? Because I is the current index that we're at. We want to add for every single T that's already in DP, we want to add nums of I to it, right? But we can't update this DP set while we're iterating through it. So, what I'm going to do is create a new DP set, basically, next DP. It's going to be the DP set that we iterate through over the you know, the next time we execute the loop. So, instead of adding to DP, what I'm going to do is add to next DP, but we also don't want to lose all the original values that are in DP. So, what I'm also going to do is to next DP, I'm going to add uh the T value as well, whatever the T value happened to be. Now, if I really wanted to, I could probably skip this line if I just took DP and cloned it and then set that to next DP, but you know, whatever you prefer. Basically, what I'm doing is taking I'm setting next DP, I'm taking every value in DP, adding it to next DP, and also adding this T plus nums of I to next DP. And once this loop executing, we're basically going to update uh reassign DP to the next DP set. And this is going to keep executing, it's going to keep executing. I is going to start at the end, and it's going to it's going to go all the way to zero. So, then we're going to have gone through every single one, and at the end, we can return true if and only if the target happens to exist in DP. Else, we have to return false. And yeah, so this is the entire code, and it runs fairly efficiently. So, this is about 50%. Now, I think it would probably be a little bit faster if, you know, the first time we find the target value, if we just returned it. Actually, let me just you know, you can probably stop watching at this point. That was the entire solution, but let me just see if this actually does speed it up. So, let's say if I happens to be equal to the target, we can immediately return true. Let me see if that does speed it up. Okay, so that actually did. So, it's about twice as fast. I think the old one was 14 milliseconds, so this is 600 milliseconds. So, this might be an optimization that your interviewer would like, but the overall time complexity is still the same, but I hope that this was helpful. If it was, please like and subscribe. It supports the channel a lot, and I'll hopefully see you pretty soon. Thanks for watching.