here's a coding interview problem from
Facebook you're given an array of unique
items so there are no duplicates in this
array and you're supposed to write a
function that takes this array of unique
items or you can see as a set of unique
items given in an array format and your
function should find all of its subsets
so for example one potential subset is
an empty set and another subset of this
entire set is the given set itself one
two and the two other subsets or single
item subsets one and two now your
function doesn't have to return anything
but it's supposed to print out all of
the subsets in say standard output and
you can print them in any order you like
so if you decide to print the empty set
you'll have an empty line to represent
the empty set and if you decide to print
a set of one after that you'll have one
comma and with a set of two you have to
come up I'm ending these lines with a
comma just for simplicity just so that
it's easier to implement your function
and if you print one two at the end
you'll have 1 comma 2 comma so that's
the problem again you can print them in
any order you like so think about this
problem for a second pause the video
right here and then come back to the
video now the first thing you might
consider when you think about this
problem is how many subsets are there
for the given array or for the given set
the answer is there are two to the part
and subsets where n is the number of
items in the array so this is going to
be 2 to the power of 2 which is 4 if n
is equal to 2 as in this example 1 and 2
and let me quickly explain why that's
the case let's say we're trying to
construct a subset out of the given
array for example 1 & 2 for us to do
that there are a few decisions that we
need to make first of all should we
include 1 the first item
in this new subset that we are trying to
construct and then the second decision
that we need to make is should we
include two in this new subset so there
are two decisions that we need to make
and for each decision or for each item
there are two available choices so the
total number of available choices for us
as we try to construct a new subset from
this given array is 2 times 2 which is 4
this number right here and it's the same
when we are trying to construct a subset
out of an array of n items as well there
are 2 choices that we could potentially
make for each item and since there are n
items there are 2 to the Parv and
potential choices or 2 to the power of n
potential subsets if we visualize this
process it might look like this with
this idea we can construct all of the
subsets by starting with an empty set
and I'm going to use this example 1 & 2
to explain this idea once we have an
empty set we need to ask ourselves
should we add 1 to this set the empty
set and if the answer is no we'll still
have an empty set and if the answer is
yes we'll have a set of 1 after that for
each of those subsets or each of those
sets we need to ask ourselves
should we add 2 to each of those sets if
the answer is yes
we'll have a set of 2 if we start with
an empty set and a set of 1 & 2 if we
start with a set of 1 and so on
and this way we can construct all of the
four subsets for this particular example
so when you see this graph you might say
well it looks kind of like a recursion
tree so maybe we can solve this problem
somehow using recursion let's see what
the solution might look like now I'm
going to explain my solution in suit
code I'm going to write a function
called all subsets which is going to
take given array as the input for
example 1 & 2 disarray and it's not
going to return anything but it will
print out
all of its subsets to construct all of
its subsets as I mentioned earlier we're
going to start with an empty set so the
first step in all subsets is going to be
initialized an empty set but to
represent each of these sets for example
this empty set and this set of one we're
going to use an array instead of a set
data structure and it's going to be
clear why we are doing this later so for
example if you have a set of two and if
you're given this array one and two a
set of two can be represented with null
and two now means that one is not in
this set and two means that two is in
this set and this way we can represent
any subset of this array with an array
of the same length so to initialize this
initial empty set at the beginning of
all subsets we can initialize an array
whose length is the same as given arrays
length or a given array that length and
the content could be anything but it can
be for example now now if the given
arrays length is 2 and we're going to
define a helper function which is going
to call itself recursively we're going
to call it helper and it's going to take
three arguments give an array which is
the given array which never changes
subsets which represents the state of
the current subset that we're
constructing so for example this empty
subset or this set of one represented in
an array format an eye is going to
represent the index of the current item
that we're examining so if I is equal to
0 for example that means that we're
trying to decide if we should include
this item in the current subset that
we're trying to construct and if I is
equal to 1 that means that we're
currently examining this item at index 1
now the first thing we need to do in the
helper function is we need to check if I
is equal to given arrays length or a
given array length if
the case for example in this example if
I is equal to two which is given arrays
length that would mean that I is
pointing outside of array which means we
already went through this whole array
and finished constructing one of these
subsets so at that point we can just
print the current subset we have with
say print subset of subset and here I'm
assuming that we've already defined a
function called print set which prints
out all of the non null items in the
given subset array and of course in our
main function
our subsets after defining an empty
subset represented as an array and
assigning it to subsets we need to call
the helper function with given array the
empty subset and 0 and of course we need
to start with 0 because that's the first
index now in the helper function if I is
not equal to given arrays length yet for
example if we're right here where I
would be 1 what should we do if I is
equal to 1 that means that we're trying
to decide if we should include 2 in this
subset that we're constructing so we'll
need to call helper twice recursively
once without adding two and the second
time after attitude to this subset now
to represent the first two recursive
call where we don't add the current item
that we're examining to the subset we
can just set the item at the current
index in the subset array to now we can
do this with subset square brackets I
equals now and after that we can call
helper recursively with given array
subset which is the updated subset I
plus one to go to the next index and to
represent the second recursive recall
where we do add the current item that
we're examining to the subset we can set
the item at index I in the subset array
to the current item for example 2 we can
do this with of course subset
square brackets I eCos given array
square brackets I and then just like
before called helper again recursively
with given array subset and I plus one
and that's my solution but what's the
benefit of using an array instead of a
set structure to represent each subset
the benefit is that it becomes easier to
keep track of the current state of the
subset by using an array instead of a
set structure for example subset might
start at now now but as we go down this
recursion tree at this point when we are
here
it'll be now two and you might ask what
happens once we go down this branch the
second recursive call from the first
call well at that point we don't have to
worry at all about the current state of
this array because once we get to the
end of this tree will override every
single element anyway so for example
once we get here this element will be
overriding with one and this element
will be now so as you can see by using
an array we have to worry less about
what the state of this subset looks like
or how the state has been affected by
previous recursive calls and this is not
necessarily the case with a set
structure it is possible to implement
these functions using a set structure
but it's just that if you do that
you need to be extra careful about which
recursive calls are made before which
ones now once you understand that
solution I'd recommend that you try
solving this problem with an iterative
solution instead so try solving this
problem without recursion at all and
once you have a good solution with that
let me know in the comment section below
also if there's any other interview
question I should cover in the future
let me know at CES dojo dot io /
contribute where you can let me know the
question anonymously ok I'll see you in
the next video