Video summary
The coding interview pattern known as "Subsets" involves generating all possible combinations or subsets from a given array, effectively creating what mathematicians call the power set. For an input containing $n$ distinct elements, such as the numbers 1, 2, and 3, there are exactly $2^n$ unique subsets because each element has two possibilities: it is either included in a subset or excluded. This includes every single-element combination like [1], [2], and [3]; multi-element combinations like [1, 2] and [1, 3]; the full set itself; and notably, the empty set where no elements are selected. A crucial aspect of this problem is that sets do not contain duplicates, nor does the order of elements matter, meaning a subset containing numbers in any sequence represents the same group as long as the members are identical.
To solve this efficiently without relying on complex bit manipulation techniques, recursion combined with backtracking is the standard approach used by programmers. The core logic involves iterating through every possible size for the subsets, starting from zero up to $n$. For each specific target size, a recursive function builds potential subsets element by element. As the algorithm adds an item to its current collection, it recursively calls itself to explore further combinations using only subsequent elements in the array (moving forward one index at a time). This ensures that every unique combination is explored systematically without revisiting previous indices within the same branch of recursion, thereby preventing duplicate sets and maintaining logical order.
Once a constructed subset reaches the desired size or completes its current path, it must be saved to a master list before backtracking occurs. Backtracking in this context means removing the most recently added element from the current collection so that the algorithm can try adding different subsequent elements instead. This process of adding an item, recursing forward, and then popping (removing) the item allows the function to explore every branch of the decision tree where each number is either included or left out. By repeating this add-and-remove cycle for all indices from start to finish, the algorithm exhaustively generates every valid permutation required by the problem statement before returning control to try alternative paths.
The resulting solution demonstrates a versatile template applicable to many other combinatorial problems in coding interviews beyond just subsets. The pseudo-code structure typically consists of a base case that checks if the current subset has reached its target length, at which point it is added to the results array and the function returns; otherwise, it loops through remaining elements, adds them to build up combinations, recurses with an incremented index, and finally removes the element via backtracking. This pattern highlights how breaking down a complex generation problem into small recursive steps—where each step involves modifying state (adding/removing) and exploring deeper levels of recursion—can simplify seemingly difficult tasks into manageable logic that scales predictably based on input size $n$.
Read the full video transcript
okay guys so the next coding interview
pattern that people normally see is
something called subsets so what are
subsets so for this it's basically just
generating all the possible subsets so
every single possible permutation or
combination or subset with whatever it
is okay so you're going to recursively
generate all the subsets now there's two
ways to do this one is to do it
iteratively using some bit masking but
the other way more normally is to go
over it with recursion so how do you do
that well first let's actually explain
what a subset is so let's say I have
given the numbers 1 two and three right
subset what they mean is like all the
possible individual sets you could have
in this array so in math it's called the
power set but let's just list all the
different possible ways so how what are
the different possible ways we could
have the numbers 1 two 3 so to have
numbers 1 2 3 we could could
have we could have uh just the number
one right that's one set right we have
number two right and the other one we
could have the number three right but
there's more to it there's more two than
that right we could also have one
two right and we could also have two
three right and we could also have 1 two
3 right and then we could also have um 1
three right because that's another set
we could have we got to pick the number
one and pick the number three right but
we also got to have the empty set right
because you could pick
nothing you pick nothing so out of all
these sets
right the generating subsets for all the
possible subsets you could have for a
set in this array is literally just how
how many different uh ways can you
choose pick a number and put it into a
set so remember the definition of a set
means that it's like an a grouping but
the there's no duplicates okay so it's
like a grouping but there's no
duplicates so you might think that you
could have the Set uh
32 but 32 is the same thing as
23 okay these are the exact same thing
32 is the same thing as 23 the ordering
doesn't matter per it it really doesn't
matter so it's the exact same thing
there's also no duplicates so we cannot
have two
two yeah so these we cannot have this is
the exact same thing as that so yeah so
uh just
ordering all the subsets you could
see right here we have one two three the
empty one two 2 3 one two 3 and 1 three
okay so how many uh numbers do we have
how many number of sets we have we have
one two three four five six seven eight
so we have eight total sets Okay but oh
wait how many numbers do we have well we
have one we have two and we have three
so we have three numbers but there's
eight so uh it turns out that the total
number of subsets that we have is um 2
to the^ of three which gets you eight so
if we have n numbers so let's say I have
uh let's say our array has like n
numbers if we have n numbers it would
just be 2 to the power of n so that's
the number of subsets right 2 the^ N is
the number of subsets so that's just a
gist of how subsets work what they are
and exactly what we're trying to do
right so as a programmer this is a math
of it right we're trying to generate
every single possible subset in this
array and see if it turns out right so
we need to we know that we need uh two
to the the power of n so if we have an
array of size n we need two to the power
of n values in our sub total subset okay
so how do we do this in with uh
recursion in programming well we do
something called backtracking plus
recursion so it's not this difficult at
all it generally has the exact same
formula of most problems so if you know
this simple formula you could apply it
to most of the problems and we could go
over as many problems as as we want CU
it's literally the same thing so I'm
going to go show you guys the pseudo
code of how this works and then let's
just explain it all right guys so how do
we generate all subsets how do we
generate all subsets to
our value or function okay so we need a
function okay so remember we have this
giant array right and uh we have our
individual array of one two and three or
values that we need to generate and we
need to put we need to generate all the
different subsets that gets put in this
giant array okay
well how do you do that well first of
all we need to generate them for every
single size so each size okay so what is
a size when each size is equal to zero
so
um when each size is equal to zero well
what is a subset with a side zero it's
just itself right and when each side is
equal to
one what are the subarrays that have
size equal to one well we have
individual one two
and three right each of these individual
subsets right have a size equal to one
right because that's what we have and
then what about the size of each size
equal to
two right well what are the different
subarrays we have the size values equal
to two we got one two 2
three and then uh 1 three right and then
we have it each size of size equal to
three right and that's our final one two
and three so every time we uh
generate our subarray or each subarray
right we need to generate them for each
of the sizes and each of the sizes will
be zero 1 2 and three okay right you
guys coming understanding what I'm doing
like each of these sizes that we're
generating it will have a size 0 1 two
and three so for that we need to have a
function that generates all the subsets
for each of these individual sizes right
you understand what I'm saying right
each of these sides we need to have a
giant function right and we need to um
call this function for each of these
individual sizes okay well so for that
we are going to have um a variable
called each size okay and each size is
going to loop from size
zero to the size of n and n will be the
size of our current array so this
current array right this current array
has a size equal of of n right so in
this case n is equal to three right we
have three elements here right we have
three elements in here right three
elements in this array so we need to
generate all the sizes right so each
size is going to loop from zero to n so
um what does that look like in the code
so basically we have our main function
right and then we're going to uh loop
through
from each
size it's going to equal to Z and we're
go up to n
right each side is going to Lo from Zer
to n and we're going to call we're going
to generate all subsets for each
size right that's what we're going to do
you guys understand what I'm say going
with this right like we got to generate
all the subst size zero 1 two three
right so on and so forth right n is n is
like the total the current number of
elements in our current array right so
we have one two and three and N is equal
to three right here you guys understand
what I'm saying yeah okay so that's what
we're going to do and in our function
gen all
subs we have to take in this value each
size right okay so um what else do we
need well um well we need to Loop
through our array we need to Loop
through our array so we need our current
index
that we're at right like if I'm looping
through one two and three
right I need my current Index right
where I'm at right remember I have to
pick numbers from their array right I
got to pick numbers from each of these
array right so I can pick the number one
I could pick the number two I could pick
the number three right so we need an
index to see which number we're picking
from right all right so that's what we
need um we need our current array right
we need our current
array our current array is just like one
two and three this is like the array
that we're doing
it and um we need our subset each subset
right remember we're generating all the
values in each individual subset like
each of these like zero one and then two
so we need like this array we need this
this subset that we're adding values to
it and then adding it to our all sub
sets right and then we pick another
value add it to it and then when we're
done generating we add it to our all
subsets right that's what we need so we
need a current
subset
okay and um yeah
so and then we need a we need a variable
for like the whole array like the whole
the giant array the giant array that has
all the subsets right remember we need
we have this giant array and it has all
the subsets like this
one two three so on and so forth right
we need that giant array that has
everything that all subsets okay
so um what is our base case well um if
our current sub subarray right or a
current
subset has a size that is already equal
to each size that we're
generating right so if our current
subset has a size that's already equal
to each size we're generating it we're
going to add it so we're going to add to
all
subsets Right add it add it to all
subsets right like when we when we're
done generating for a size zero then we
add it to all our subsets right when
we're done generating a size one we add
it to all the subsets we're done
generating with size two we add it to
all subsets right that that's basically
the gist of it right and then well we're
going to return so we're going to exit
it return okay so that's this part of
the pseudo code okay um the main method
I'm going to just like slowly highlight
it okay so add all subsets um otherwise
what are we going to do well we need to
Loop through each of the individual
values that we're generating so we're
going to Loop through from um each
individual values so let's say I'm at
the current value of one right a current
value one well I need to add it
to my um my array my array I need to add
it to my array
so uh I picked the number one I need to
add to my array right and then I need to
pick the number two and I add it to my
array then pick number three add it to
my array right but then also I need to
pick the value two added to my array and
then I could pick the value three added
to my array right and I could pick
number one added to my ARR and number
three added to my right so there's a lot
of combinations we got to do right so um
what are we going to do we're going to
loop from
let's just call A J we're going to loop
from our current
index to the
end right of our current array and we're
just going to add it to our current
subset so current
subset add the the value the current
value of
J
to our current subset right so we got to
add this so we add the current our
current value that we currently at add
it to our subset and yeah makes sense
right but then we also have to
recursively go to the next element okay
because when we're already at the number
one and we Loop through one two and
three right next time we could start at
two right and then Loop through two to
three and next time we can start at
three loop from three to three to the
end right so what do we need to do um we
need to call gen all
subsets and this time we're going to
start
from we're going to do the same thing
each size and everything but we need to
start from index plus one
now okay because that's the next value
of our array right the the next value of
array that's the next value that we have
for our array right we generate all
subsets we add
add the next value right that this time
we're starting from two instead so first
time we started from one and we Loop to
the end add all those values that have
uh this current size is equal to one or
zero one two whatever then we this time
we need to start at two right start at
two and go to the end of the array add
those values that have the size of two
so on so forth then we have to start at
the value three and then add and so on
and so forth right so that's why we got
to go to the next value that's why index
plus one um but now after we generated
added that current value we also have to
there's a case where we have to remove
it so we need to remove
it
remove current
value A
J
from
array and why do we have to do that
because there are certain cases where
let's say I picked the number two but
there's an array that doesn't have the
number two right like remember we had
like
um let's say we had one one remember we
have our total array has 1 two three
right like our current array has one two
three right well if I pick the number
one and
two right there's also an array that
doesn't have the number one right and
that just has a number two so in that
case we have to remove the last element
from our array every time we're
generating because there's a certain
situation where we have it inside and
then we generate all the rest of the
numbers but then there's a certain
situation where we don't have it so we
generate so we remove it from all the
numbers okay so yeah and I believe
that's the rest of the pseudo code
actually
so yeah I hope you guys enjoy this uh
understand what I'm going at but
basically the gist of it is that we have
we need to generate all the different
sizes of it right so we're going to have
a function that passes in each of the
size and it's going to go from zero to n
we need a current variable called a
current subset and we're going to expand
it like we're going to keep adding
values to the subset and we're going to
remove values from the
subset okay so we're going to keep
adding current values from a subset and
we're going to remove values from the
subset right why why We're looping from
the beginning to the end okay and uh if
we reach our current size like if we
reach our current size of of uh length 1
2 3 all the different sides that we need
to generate um we're going to add our
current subset to all
subsets okay we're going to add our
current subset so add current
subset to all subsets and then we're
going to return we're done then we got
to generate the next next one like next
size so on and so forth so yeah that's
the all the gist of the pseudo code
right so let's actually just type this
out again let's actually type this out
so yeah this is basically the pseudo
code okay and I I didn't include
variables in the in the in the function
because like yeah I don't know but you
have to declare those variables yourself
but yeah if our current subset has size
our size that we generate is equal to
each size right that we're generating
we're going to add it to our current
subset to all subsets and we
return now um otherwise we're going to
loop from J we're going to loop from our
J from our current index that we're at
to the end of the length of the array um
we're going to add our current value at
at J right our current any each of the
value at J to our current subset we're
going to generate all all subsets from
index plus one now from the next value
of our index and then we're going to
remove our current value of J from our
current subset okay so that's the gist
of this whole code right and then in our
main function we're going to call
like remember we're going to call all
subsets where we pass in each size is
going to loop from zero to n okay so
yeah that's the gist of the code that's
a bit gist of the pseudo code how it
works and I I'll show you guys the
actual code all right so in our main
method right of subsets we have our
current VAR value of uh nums which is
our array n is going to equal to the num
the size of our current array right and
we're going to generate all the subset
subsets for each size so each size is
going to start from zero and we're going
to go a loop up to and including n each
time and we're going to call our
function generating all subsets okay and
then we need to create a new array
because that's the that's basically the
current subset that we're having
okay so now in this function backtrack
which I call the backtrack here but you
could call it whatever you want remember
in our pseudo code it was like generate
all subsets but you could call whatever
function you want okay if our current
size is equal to each size that we're
generating um all sub sets which is This
Global variable that I declared up here
that is a 2d array of all subsets we're
going to add it so we're going to push
back the current subset that we're we
have so I call it C here C is the
current subset that we have right then
we're going to add it to it and then we
return okay otherwise we're going to
Loop through J is going to equal to the
index our current index for each value
that we're at and we're going to Loop up
to um size n size n right and do
j++ and what we're going to do is each
time we're going to add the current
value of uh nums of our current value
that we're on to our current subset of
current right push back which is adds it
to the end of it of our current subset
and then we're going to call we're going
to call backtrack right but this time
we're going to pass in j+ one which is
the next value the next generating the
next value of our current subsets and I
use the same same variables in here and
then I need to remove it so I call Pop
back so removes the value that we just
added at the end and then we're done and
that's basically a gist of generating
all subsets and you could use this exact
same pseudo code for almost all all
Every Other problem you can use it okay
generally all the problems have this
sort of pseudo code right we have a
current current uh subset we need to
generate right for all the different
combinations all size of each
combination and if it's equal to the
size that we generated we're going to
add it to all the combinations right and
if it's we added it we're going to
return we're done otherwise we got to
Loop through it and add each individual
value to it in in individual subsets and
we go to the next one go to the next
value and remove it from our current
subset and so on and so forth but yeah
that's that's the gist of it that's the
gist of this code um I hope you guys
understand this video it took uh it this
was like kind of hard to explain but
this is a cool concept for you guys to
understand yeah rate comment subscribe
I'll check you guys later
peace