If you're enough on the air with that, I'm Pro Ming.

I'd recommend my dynamic programming introduction video first.

So here's the problem.

You're given an array off integers, for example, 246 and 10.

And you're supposed to find substance of this array, which add up to a certain number for example, 16.

So in this case, there are two such substance.

The 1st 1 is six on 10.

On the second serve subset is 24 and 10.

And just to make the problem a little bit simpler, you don't have to actually find the subsets themselves.

You just need to find the number of substance that add up to the given number.

So in this example, your function should take this number 16 as well as disarray on return to because they're too subsets of this array that add up to 16.

Now, when you're given a quoting in to be a problem like this one, the typical first step is to ask some clarifying questions so you might ask as a clarifying question.

Is it possible to have negative numbers here?

The answer's no.

We only have policy interests here, so there's no zeroes or negative numbers on.

Is this array already sorted?

Actually, doesn't matter too much if it's sorted or not.

But let's just say it's sorted on.

Are there any duplicates in disarray?

So is it possible to have two of the same number?

The answer is no.

There no duplicates on what if you're given instead of 16 dero as one of the arguments, Why should we return then?

In that case, you should return one from your function because technically, the empty array or the empty set as up to zero.

So you can't just this set on you return one from your function.

So think about this problem for a second and then come back for a solution.

So if I was given this problem, I would first ask myself, How would I solve this problem on a white board or on paper?

The way I would do that is I would start with an empty set, and I would try under construct all the possible subsets of this array.

So for the right most element, or you can start at the left most element.

But let me start with the right most element for that one.

We need to ask ourselves, Do we want to include it in the subset that we're trying to construct?

If the answer is yes, will have a subset off just one element 10.

And if the answer is no will still have on empty set on, we'll need to do the same thing for the next element.

Six.

And for each of these subsets.

So if we decide to include six to this subset or add six to this upset, we'll have six and 10 on.

If we decide not to include that in, this one will have to sten and so on.

So, just like that, you'll be able to find all the possible subsets off this entire rate on for each of these subsets.

You could just ask yourself, in theory, does it add up to, for example, 16 and then add up all of those subsets and we have the answer.

And when I see this structure, if I was in the actual interview, I might say Well, since it says it's a tree, it actually looks like a rickerson tree, and so maybe I can solve this problem using the courage in.

So let's see how we can do that.

Of course, the idea of Rikers on Ace to break down the large problem, the original problem into smaller sub problems that are similar in nature.

So let's see how we can do that.

Let's call the number of substance that add up to 16 out of the entire E, and that's the answer that we're looking for on this end is actually the sum of two numbers.

On the first such number is the number of subsets that add up to 16 which include 10 on the second sits number.

It's the number of substance that out of 2 16 which do not include 10 and actually this first number.

The number of substance that add up to 16 which include 10 is equivalent to the number of substance that out up to six out of these three elements.

So the substance that out up to six out of these three elements are 24 on dhe, just six, and you can sort of merge each of these subsets with this subset with only 10 and get a subset that as up to 16 we can get two of them.

So we can put to here as the first summer on the second number that the number of subsets that add up to 16 which do not include 10 is equivalent to the number of subsets that add up to 16 out of thes three elements.

Because we don't have this in play anymore.

And there's no such subset that as up to 16 out of these three elements, because if you add all of them up, you'd only have 12 as the total sum.

So you have there right here is the second number.

So in this particular example, he also that we're looking for is and is equal to two past era, which is too.

So what we just did as we broke down the large original problem off finding the number of substance that add up to 16 out of this whole array into two smaller sub problems.

And we can actually keep going like that further down the tree as well.

Just keep breaking down the problems into smaller and smaller problems.

So this is the basic idea off my recursive solution.

But one thing to note here is that you don't really have to create or store these individual substance because we're only interested in the number of subsets that add up to a certain number.

For example, 16.

We only need to store the some off each subset.

So the Somme off this upset would be 10 and then the some off the empty subset is, of course, zero on the Somme off.

This one is 16 and the sum of 10 is 10 and so on.

Okay, let's now see what this solution might look like.

Code.

Okay, here's my recursive solution.

In code, I'm defining two functions here counts.

It's and wreck count sets will be our main function.

You'll take the array discovery on the total amount that we're trying to find the substance for, and this is going to return the number of substance that add up to the total amount and then wreck will be our recursive function, so it'll call itself with personally on.

It'll take the given array, the total amount and I as an index, and this is going to return the number of substance that add up to the total amount.

But while considering on Lee the elements up to the next I so if you're given, for example, disarray are on six as the total amount on to as the index, that would be right here.

We're only considering these three elements to find the success that add up to a given amount.

And in that case, your function wreck should return to because they're too such substance to four on six.

Both of them add up to six.

And the only thing we need to do in count sets is to return wreck with.

The arguments are a total on our doubt length minus one, because our that length minus one would be the last index officer rate.

In this particular example, that would be three.

Okay, the first thing we need to do in the rec function or the Rikers to function is we need to take care of some base cases.

The 1st 1 to take care of is when total is equal to zero.

In that case, we should return one, because when totally is zero, the only substance that adds up to Dara is the empty substance, and there is only one of them on the second base case to take care of age when total is less than zero.

And if that's the case, there's no subset that as up to zero, so we should just return zero.

Since there are no negative numbers in disarray on def I iss less than there that with me, I is already outside of the saree and since we know that total is neither zero nor less than zero total, here is a positive number and since we don't have any more numbers to create a subset with that add up to hopefully total will just return there on.

If none of these cases are true, will then go to our recursive cases.

The first recursive case that we need to deal with is when total is less than our score buckets I or the lasts item though we're examining.

So, for example, if I is equal to two with the examining this item six would be devalued off our school brackets.

I.

And if the given total here is, let's say, four, there would be no way of finding us upset out of thes three elements that add up to four, which includes the current Item six.

So that means the number of substance that add up to the total amount out of these three elements is equivalent to the number of substance that add up to the tour.

Amount out of these two elements is that to express that will just need to write return wreck or a total I'm minus one.

So are on total or on taste on.

We'll just need to go to the next item or the item that's left to the current item that we're examining.

Other case we need to deal with is everything else.

So let's say I is equal to two here.

So we're examining this item currently on the total that we're looking for is six.

If that's the case, we'll need to deal with two different cases.

Just like I explained before.

The first case is when we don't include a six in the substance that we're trying to construct on.

It's the same as before, so we'll just need to write wreck our total I am minus one on the second case is when we do include this item in the subset that we're trying to construct, and just like I explained before the way you can think about it.

Is this the number of substance that add up to the given total six right here, which include this Number six is equivalent to the number of substance that add up to total minus the current item.

So total minus R square brackets.

I out of thes two elements on Lee so you can find that with wreck or total minus our score brackets.

I.

So that will be the new total that will be looking for subjects for on.

I'm on this one to go to the next element, and that's my recursive solution, okay?

And the solution works, but the problem is it's not very efficient.

The problem is that we're gonna call dysfunction wreck with the same arguments are a total, and I over and over again.

And this will be particularly the case when given array is very long, very large, and the given total is very large as well.

So, of course, dynamic programming says, why not just store some of those return bodies for the same total, and I, so that we don't have to repeat the same competition over and over again?

So let's see what a dynamic programming solution or a meme wised solution looks like in code.

Okay, here's mine.

Dynamic programming or memoir.

It's solution.

Just like before we're gonna write to functions.

DP on counts.

It's DP concepts.

DP will be our main function, which will return the number of substance that add up to total.

Given the Array and DP will be the function that will call itself recursive Lee.

But note here that we have additional argument here called meme, which we're going to use to store the return values for some arguments for dysfunction.

The first thing we'll need to do in count sets DP is we need to initialize an empty additionally, or half stable, depending on the language on their assigning to mem.

Because this is what we're going to use for storing the return bodies and then call DP with the arguments are total.

Are that length minus one and their men okay in DP, The return volleys for certain arguments will be stored in mem in key value pairs.

Each key will represent a unique set off arguments and there will be an associative value with it, and that's going to be the return value that's stored for this function.

DP.

So we need a way to create a key which is going to be a string in this particular case from the pair or arguments that changed Total and I There are several different ways of doing this.

But what we're going to use here is a very simple method.

We're going to convert Total and I, which are intruders.

Two strings and then we're gonna come.

Captain ate them with the collar in between them.

So, for example, if we had 10 as total on three as I, we'll have this string 10 call on three as the key, and we don't necessarily have to use this particular strength, but we just need a way to uniquely identify each argument pair with a strength.

And then if this key already exists in Mem, that would mean that we've already calculated the return body for this particular total.

And I pair So we're just gonna return the store value the value that's associated with this particular key instead of going through this whole function on.

If we don't have any story Valley associating with this key yet, we're gonna go through this whole function on.

It's gonna be very similar to what we had earlier for the recursive solution.

First of all, the base cases are exactly the same.

So we're just gonna skip that on else If total is less than our Scott brackets, I we have dp off our total are minus one meme, which is almost exactly the same as what we had earlier in our recursive solution.

But instead of returning this right away, we're gonna store it and the two return viable, and then we're going to return it at the end.

And we're gonna take care of the other case the same way we have dp off our total minus our scar brackets.

I I'm gonna swim Mem And then the same thing asked why we had right here.

So add them up on Instead of returning it, we're gonna store it in to return.

And after that, before returning to return, we're gonna story and the meme dictionary or hash table with the key key, which we calculated earlier.

So that weekend use this fiery later when we see the same pair off arguments on.

Of course, at the end of this function, we're gonna return to return on.

We're done.

This is my dynamic programming solution, but let's see if we can calculate the time complexity for this function.

To find the time complexity for this method, we first need to find a number of times.

We call our a recursive function dp and then multiply by the time it takes to execute each of those costs.

So let's first see if we can count the number of calls we call.

They pee.

There are only two ways we call the P.

The 1st 1 is from right here from the original function counts sets dp, and then the second way is from this block right here, either on this line or this line.