hey everyone in this video I'm gonna
give you a programming slash coding
interview problem for which you can use
dynamic programming if you're not
familiar with then I'm roaming I'd
recommend my dynamic programming
introduction video first so here's the
problem you're given an array of
integers for example 2 4 6 and 10 and
you're supposed to find subsets of this
array which add up to a certain number
for example 16 so in this case there are
two such subsets
the first one is 6 and 10 and the second
such subset is 2 4 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 subsets that add up to the
given number so in this example your
function should take this number 16 as
well as this array and return 2 because
there are two subsets of this array that
add up to 16 now when you're given a
coding interview 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 is
no we only have positive integers here
so there's no zeros or negative numbers
and is this array already sorted
actually it doesn't matter too much if
it's sorted or not but let's just say
it's sorted and are there any duplicates
in this array so is it possible to have
two of the same number the answer is no
there are no duplicates and what if
you're given instead of 16 zero as one
of the arguments what 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 count just this set and
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 whiteboard or on paper
the way I would do that is I would start
with an empty set and I would try and
construct all the possible subsets of
this array so for the rightmost element
or you can start at the leftmost element
but let me start with the rightmost
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 we'll
have a subset of just one element ten
and if the answer is no we'll still have
an empty set and 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 subset we'll have six
and ten and if we decide not to include
that in this one we'll have just ten and
so on so just like that you'll be able
to find all the possible subsets of this
entire array and for each of these
subsets you can 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 since it's a tree it actually
looks like a recursion tree and so maybe
I can solve this problem using recursion
so let's see how we can do that of
course the idea of recursion is to break
down the large problem the original
problem into smaller subproblems that
are similar in nature so let's see how
we can do that let's call the number of
subsets that add up to 16 out of the
entire array and that's the answer that
we're looking for and this n is actually
the sum of two numbers and the first
such number is the number of subsets
that add up to 16 which include 10 and
the second such number is the number of
subsets that add up to 16 which do not
include 10
and actually this first number the
number of subsets that add up to 16
which include 10 is equivalent to the
number of subsets that add up to 6
out of these three elements so the
subsets that add up to 6
out of these three elements are 2 4 and
just 6 and you can sort of merge each of
these subsets with this subset with only
10 and get a subset that adds up to 16
we can get 2 of them so we can put 2
here as the first number and 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 these three elements
because we don't have this in play
anymore and there's no such subset that
adds 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'd have 0 right here as the second
number so in this particular example the
answer that we're looking for is and is
equal to 2 plus 0 which is 2 so what we
just did is we broke down the large
original problem of finding the number
of subsets that add up to 16 out of this
whole array into two smaller subproblems
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 of my recursive solution but
one thing to note here is that you don't
really have to create or store these
individual subsets because we are only
interested in the number of subsets that
add up to a certain number for example
16 we only need to store the sum of each
subset so the sum of this subset would
be 10 and then the sum of the empty
subset is of course there
and the sum of 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
in code okay here's my recursive
solution in code I'm defining two
functions here count sets and rec count
sets will be our main function it will
take the array the SKU an array and the
total amount that we are trying to find
the subsets for and this is going to
return the number of subsets that add up
to the total amount and then rec will be
our recursive function so it will call
itself recursively and it'll take the
given array the total amount and I as an
index and this is going to return the
number of subsets that add up to the
total amount but while considering only
the elements up to the index I so if you
are given for example this array r & 6
as the total amount and 2 as the index
that would be right here
we're only considering these 3 elements
to find the subsets that add up to the
given amount and in that case your
functional rec should return 2 because
there are two such subsets 2 4 & 6 both
of them add up to 6 and the only thing
we need to do in count sets is to return
rec with the arguments or total and our
dot length minus 1 because our dot
length minus 1 would be the last index
of this array in this particular example
that would be 3 okay the first thing we
need to do in the rec function or the
recursive function is we need to take
care of some base cases the first one to
take care of is when total is equal to
zero in that case we should return 1
because when totally is zero the only
subset that adds up to zero is the empty
subset and there is only one of them and
the second base case to take care of is
when total is less than 0 and if that's
the case there is no subset that adds up
to 0
so which is just returned zero since
there are no negative numbers in this
array and if I is less than zero that
would mean I is already outside of this
array 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 we'll just return zero and if none
of these cases are true we'll then go to
our recursive cases the first recursive
case that we need to deal with is when
total is less than our square brackets I
or the last item that we are examining
so for example if I is equal to two we'd
be examining this item six would be the
value of our square brackets I and if
the given total here is let's say four
there would be no way of finding a
subset out of these three elements that
add up to four which includes the
current item six so that means the
number of subsets that add up to the
total amount out of these three elements
is equivalent to the number of subsets
that add up to the total amount out of
these two elements instead to express
that we'll just need to write return rec
or total I minus one so or on total or
unchanged and we'll just need to go to
the next item or the item that's left to
the currently item that we're examining
our case we need to deal with is
everything else so let's say I is equal
to 2 here so we're examining this item
currently and the total that we're
looking for is 6 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 6 in
the subset that we're trying to
construct and it's the same as before
so we'll just need to write rec or total
I minus 1 and the second case is when we
do include this item
the subset that we are trying to
construct and just like I explained
before the way you can think about it is
this the number of subsets that add up
to the given total six right here which
include this number six is equivalent to
the number of subsets that add up to
total minus the current item so total
minus R square brackets I out of these
two elements only so you can find that
with rec or total minus RS square
brackets I so that'll be the new total
that we'll be looking for subsets four
and I minus one to go to the next
element and that's my recursive solution
okay and this solution works but the
problem is it's not very efficient the
problem is that we're gonna call this
function rec with the same arguments or
total and I over and over again and this
will be particularly the case when the
given array is very long very large and
the given total is very large as well so
of course then IMing programming says
why not just store some of those return
values 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 memorized solution looks like in
code okay here's my dynamic programming
or memorized solution just like before
we're gonna write two functions DP and
count sets DP count sets DP will be our
main function which will return the
number of subsets that add up to total
given the array and the P will be the
function that will call itself
recursively but note here that we have
an additional argument here called mem
which we're going to use to store the
returned values for some arguments for
this function the first thing we'll need
to do in count sets DP is we need to
initialize an empty dictionary or hash
table depending on the language and then
assign it to mem because this is what
we're going to use for storing the
return values and then call DP with the
arguments our total or
length minus one and then men okay in DP
the return values for certain arguments
will be stored in ma'am in key value
pairs each key will represent a unique
set of arguments and there will be an
Associated 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
integers to strings and then we're going
to concatenate them with a column
between them so for example if we had 10
as total and 3 as I will have this
string 10 colon 3 as the key and we
don't necessarily have to use this
particular string but we just need a way
to uniquely identify each argument pair
with a string and then if this key
already exists mmm that would mean that
we've already calculated the return
value for this particular total and I
pair so we're just going to return the
stored value the value that's associated
with this particular key instead of
going through this whole function and if
we don't have any stored value
associated with this key yet we're gonna
go through this whole function and it's
going to 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 and
else if total is less than or square
brackets i we have DP of our total i
minus 1 mem 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 to return variable 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 of our
total minus R square brackets
I - 1 min and then the same thing as
what we had right here
so add them up and instead of returning
it we're gonna store it and to return
and after that before returning to
return we're gonna store it in the ma'am
dictionary or hash table with the key
key which we calculated earlier so that
we can use this value later when we see
the same pair of arguments and of course
at the end of this function we're gonna
return to return and 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 the number of times we call
our recursive function DP and then
multiply by the time it takes to execute
each of those calls
so let's first see if we can count the
number of calls we call DP there are
only two ways we call DP the first one
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 now the
important thing to notice here is that
the number of times we call this block
is at most total times and times where n
is the number of items in the given
array and you can think about it this
way there are any potential values for I
ranging from 0 through and minus 1
and the number of potential values for
this argument total is the original
value of total so if the original value
of total is 16 and if you're given this
array and would be 4 so you'd have 16
times 4 potential value pairs for the
pair total and I and for each unique
pair we only go through this entire
function and then get to this block once
because after the first time will
already have returned here and if either
total or I is out of range from those
particular
for example if I is minus 1 then we'll
already have returned before we get to
this block for example right here as
well and so we get to this block at most
total times n times and each time we get
to this block will call DP only at most
twice so the maximum number of times
we're gonna call DP is going to be total
times and times 2 and if you want you
can add 1 to account for the first time
we call DP from count sets DP so now we
have an upper bound for the number of
times we're gonna call this function DP
and that's total times n times 2 plus 2
and of course total here is the original
value of total and what about the time
it takes to execute each of those calls
if you look at each line in this
function except for those recursive
calls each line only takes a constant
amount of time or Big O of one to
execute and of course when you add up a
bunch of different operations each
taking constant amount of time they will
only take a constant amount of time as a
whole so the time it takes to execute
each of those calls excluding those
recursive calls is Big O of one or a
constant amount of time and when you
multiply these two numbers together Big
O of 1 and total times n times 2 plus 2
you get Big O of total times n and being
the number of items in the given array
and so that's the time complexity for
this particular function ok just like
usual let me know in a comment below if
anything is unclear and if you like this
video I would also recommend my course
on udemy called 11 essential coding
interview questions in which I cover 11
of the most essential coding interview
questions to master although I don't
cover dynamic programming in this course
but I'm gonna put a link to this course
in the description below and if you want
to make sure that you don't miss my
future videos the best way to do that is
to subscribe to my newsletter by going
to CS dojo dot io / news
my K from CS dojo and I'll see you in
the next video