Understanding Subsequences with Recursion: Guide + Code Example

Convert to note

What is a Subsequence?

A subsequence is a sequence that maintains the original order of elements but does not have to be contiguous.
For example, from array [3, 1, 2]:
- Contiguous subsequence: [3, 1]
- Non-contiguous subsequence: [3, 2]
- Empty subsequence is also valid.

Difference: Subsequence vs Subarray

Subarray: contiguous elements only.
Subsequence: ordered elements that may be non-contiguous.

Problem Statement

Given an array, print all its subsequences.
For an array of size n, total subsequences = 2^n.

Recursive Approach (Take or Not Take)

At each index, decide to either 'take' the element or 'not take' it.
Use recursion to explore both possibilities for every element.

Recursive Algorithm Structure:

Base case: When index == n (end of array), print the current subsequence.
Recursive calls:
- Include current element and recurse for next index.
- Exclude current element and recurse for next index.
Backtracking:
- After including an element and returning from recursion, remove it before exploring the 'not take' path to keep the subsequence correct.

Example Walkthrough

Array: [3, 1, 2]
Start with an empty subsequence and index 0.
Recursion tree explores:
- Take 3 → Take 1 → Take 2 → print [3,1,2]
- Take 3 → Take 1 → Not take 2 → print [3,1]
- Take 3 → Not take 1 → Take 2 → print [3,2]
- Take 3 → Not take 1 → Not take 2 → print [3]
- Not take 3 → Take 1 → Take 2 → print [1,2]
- Not take 3 → Take 1 → Not take 2 → print [1]
- Not take 3 → Not take 1 → Take 2 → print [2]
- Not take 3 → Not take 1 → Not take 2 → print [] (empty)

Code Snippet (C++ Style Pseudocode)

void printSubsequences(int index, vector<int>& arr, vector<int>& ds, int n) {
  if (index == n) {
    // Print current subsequence
    if(ds.empty()) cout << "Empty subsequence" << endl;
    else {
      for (int x : ds) cout << x << " ";
      cout << endl;
    }
    return;
  }
  
  // Take the current element
  ds.push_back(arr[index]);
  printSubsequences(index + 1, arr, ds, n);
  ds.pop_back(); // Backtrack

  // Not take the current element
  printSubsequences(index + 1, arr, ds, n);
}

Time and Space Complexity

Time Complexity: O(N * 2^N) where N is the array size (2^N subsequences, each printed in O(N)).
Space Complexity: O(N) for recursion stack and temporary subsequence storage.

Key Takeaways

Understand the difference between subsequences and subarrays.
Utilize the 'take or not take' recursion pattern for generating subsequences.
Backtracking step (removing last added element) is crucial for correctness.
Drawing recursion tree helps visualize recursive calls.

Closing Notes

Mastering this recursion pattern is useful in many combinatorial problems and dynamic programming challenges. Practice by drawing recursion trees and coding the approach for various input arrays for deeper understanding.

For broader foundational concepts, consider exploring Comprehensive C++ Basics and Interview Prep with Striver's Resources to strengthen your understanding of C++ recursion and data structures.

hey everyone welcome back to the channel i hope you guys are doing extremely well so in the previous video we did learn

about multiple recursion calls so where is that

specifically used now you'll find in recursion a lot of questions or internet programming a lot of questions which

does involve this particular term which is known as subsequences now what is the definition

of a subsequence a sequence uh i or i can say a contagious or a

non-contagious sequence it can be a contiguous it can be a non-contagious

sequence which follows the order this is very important which follows the

order this is what we call as a subsequence a sub array is just contagious but a sub

sequence can be contagious as well as non-contagious let's understand if i give you an array which is something

like three one two okay this is an array of size three if i ask you subsequence i can say three is a subsequence i can say

one is a subsequence i can say two is a subsequence i can say 3 1 is a subsequence i can say 1 2 is a

subsequence i can also say 3 2 is a subsequence i can also say 3 1 2 is a subsequence i hope that makes sense this

is a contiguous contagious contiguous contiguous contagious but over here three and two as a non-contiguous

subsequence but still it's a subsequence three one two is a subsequence but at the same time i cannot say three to one

to be a subsequence because it's not following the order you have to make sure it follows the order of the array

the order of the array is three has to be before one one has to be before two this is the order of the array so please

make sure like if you're taking three two three has to be before two in the array

so order has to be maintained in order to call it as a subsequence now apart from

three two everything other is a sub array so a sub array can be a subsequence remember this so all of

these are subsequences and also we can call as an like nothing an empty

set as a subsequence also because we are not picking up any elements from the array that can also be called as a

subsequence so in total in total there are eight subsequences for this n equal to three size array and i want you to

write a function which pins down all the subsequences now this can be uh done using a very very famous algorithm power

set for which i've already made a video you should definitely check it out how to do

it using powerset but over here since we are learning recursion we will not be doing that we

will be learning the recursive way okay so let's first understand some pattern

now the array was uh 3 1 2 and i say that 3 comma 2 is a

subsequence now let's observe a pattern okay let's observe a part so the pattern is very

simple there were three elements there were three elements and i say that

three i've taken three i have not taken one and i've taken two

so if i do a take and a non take on indexes

this index i'm taking this index i'm not taking this index i'm taking and if i do this then this is 3

and this is 2 hence i can get this particular subsequence

so that's the pattern for an example i say that okay how will you get this one comma two subsequence again very simple

not take take and take correct if i ask you how will you get three comma one again very very simple

take take not again if i ask you how will you get

three one two very simple take take take again if i ask you how will you get

null not take not take nothing so what i am observing is

for every index i have a couple of options either i say that i'm gonna take it i'm not gonna take it so depending on

this i will try to solve this problem okay so you've got the intuition now let's uh look at the code

if specifically my task was to give you the intuition now let's uh look at the code and this structure of code that i'm

going to write is gonna be significant in going forward like you will see all the problems being solved using this

particular structure of code so you need to understand the structure of koda it's a pattern that you have to keep it in

your head every day tell your anyways let's get started so

we will always have an index remember this we will always have an index so by the way just assume the array to

be three one two assume the array to be three one two with indexes indexed as

zero one two so assume you have an index and we have a data structure it

let's assume it's a list in java

in c plus plus it's a vector okay so i've taken a array or list or whatever you wish to

so what i'll say is okay i know

i'll have to start from three i'll have to go to one i'll have to go to two correct

so specifically i have to go till index two that's for sure i have to go till index two there is no way that i can

avoid that so i can say my base cases

if the index by chance is equal to equal to n or crosses n i'll

stop or i'll print it rather i will print the array

and i will return that's what my base case will be

apart from the base case what will i say i'll be like okay

please add in the array this particular guy

array of index or i can say whatever list you are carrying or i can say whatever list you are

carrying please dot add in java you can use add in c plus plus

you can use pushback and vector dot add array of i

correct next you will be like function

index plus 1 comma this particular list that you're carrying

and whenever you this requestion will go and will come back correct so whenever you uh come

back you'll be like let's remove this particular guy

let's remove this particular guy why are you removing i'll explain you don't worry don't worry about that

next you will like let's go with the same list

right this is what the code will look like and the structure has to be in your mind always

okay this is the case of take this is the case of not take okay now let's understand how

this code works using a main function so if i write a main function and i'm

assuming you have the array as 3 1 2 rather

and then you call this function with index 0 and uh empty array okay

so what will happen is this function this function basically calls this particular guy if i just shrink it down

this particular guy correct next whenever this guy is called the

index value is zero this is an empty array right

this line is no more not executed because n is apparently three because the size of the array is three

next you say in the array add it so your array will now contain the first element which is

three next you say let's call the function

say calling the function stating index plus one which you are saying that okay what i've done is i've taken the

zeroth index yes i've taken three let's move to the next index which is one and please pass on the array three

so this this particular array remember this this particular array is the sub sequence that you're trying to form

so we went to event over here right now again the if base case will not be executed

and you will again say in three any please add is can you please add array of index of one

thereby thereby this will make sure that the array is now

three comma which whichever is at the index one which is one after that you'll be like let's do f of

index plus one which is two comma with the array three comma one now this function call will go

please please understand indeed next f 2 comma

3 comma 1 is the array the base case will again not be executed the base case will again not be executed

what will be the next step i'll say again array 3 1 can you please add

array of 2 which is this time this 2 so please add it so your array

becomes 3 1 2 perfect let's so you have done for this let's call the next one index plus 1 is 3 with the array 3 1 2

perfect now this will call another recursion

with f of 3 array as 3 1 2 correct

now this time the base cases if index is greater than equal to n and it's true and it's true

and you're like print the array print this particular guy

so i can say if i if i'm maintaining an output screen yes if i'm maintaining an

output screen for the first time i will get three one two printed

correct now you'll be like okay you have printed

now it's time to return so let's return you have returned now if you have returned

time to understand your array is having three one two for the last index you decided that this two yes this two has

to be picked but you still have an option where you say

you did come up with three one what if i do not pick the last index then the subsequence will stay as three

one because logically you came up with three one and you wanted to decide for the last

index and i said okay please pick it so you got three one two and i can say please do not pick it so i'll get the

subsequence three one so in this way you can get both the subsequences so over here

since you have added since you have added two has been added right 2 has been

added you need to remove it that's why we say 3 1 2 please please remove

array of like whatever is it since it will be at the last index you

can just remove the last index which is array of index two this is why you remove after removal the array again

becomes three one back to the state it was back to the state it came it came as three one it is back to that state once

it is back to the state you call the next index saying it's back to the state i'll decide for this index i'm not gonna

pick anything so please go with three one had you not removed had you not removed

then that would have been 3 1 2 and you'd have passed this which would have been wrong so this time you call this it

goes f 3 3 1 and this time again the index

greater than equal to three true print and return so this time the printing will go and return so that this

time the printing will happen for three and one okay just remove this the printing will

happen for three and one so i will be over and i'll go back and once this is over i

can easily come back let's come back over here now when you're coming back

you realize you went with three one and you decided for the last index

now you are at a position where you have a three one right so

you have a three one and you have done for this guy where you have set key one will be taken now i'll say let's remove

this one thereby the array again becomes three what are the options whenever you're

saying someone is coming up with three what are the options for this particular guy you said okay

please take so you got three one now you'll say do not take so you'll get

three and then you can go on designing so in this way yes in this way can i say i can easily do it so you'll remove

and again you will call for f of two radha and he'll call on with only three so

this time again the call will go to f of two with three

and again the same task will happen for the second index because this time you're coming with three nothing and

this time you will again do a take so three comma two will happen and you'll say not take so only three will

happen so in this way every other sub sequence can be easily formed so i hope you have understood the entire concept

how the first call goes then comes how this call goes and comes but the critical portion over here was to

understand the remove i'll give you a classical example to remember this

stuff now imagine uh this is the trial room of a shopping mall okay and you went in there

now tell me one thing if you have taken couple of clothes assuming over here couple of clothes is

nothing but i'm saying take or not think you've taken a couple of clocks whenever you're trying the first cloth where this

in this case is like picking up the first item you will have to take out your current

dress you'll take it off and you'll wear the new clothes correct in order to wear the next set of clothes

you have to again take it off now if you don't take it off how will you wear but this is why

if you have added it over here understand if you have added this guy so this guy has been added so in order to

try non addition you have to remove this now that's why it will be removed that's the concept of

non removal so in this way you can draw the entire stuff but i'll try to explain you this using a

recursion tree because that is how we will be doing across so let's take the array as three comma

one comma two okay so i've taken the array as three comma one comma two

and this time let's take the recursion tree as f of zero and an empty data structure

so initially at the zeroth index maybe like i can try that means i can pick up three so if you pick up three you'll

move to the next index because for the zeroth index you have picked up so your data structure will only be containing

three or you can say i will not pick up hence the data structure will be moving empty

to the index one correct now over here whenever i say f of zero and f of one and f of one over

here you need to understand this function call was made previously and then it came back so this

three yes this three which is added has to be removed has to be removed and then this function call will be made

you need to understand this is how this pans out to be so what i'll now do is i will super super quick uh draw the

recursion tree so it's f of zero empty data structure you say pick so you'll be like f of one

pick three you'll be like not pick like f one do not pick empty data structure you'll be like pick first index do not

pick this first index f of two three of one this will be f of two

three of zero nothing again you'll be like

pick not pick this would be f of three three one two so whenever you reach the

third index yes whenever you reach the third index this can be printed so i'm just marking it as green that means it

is printed then you go back this time this recursion call will come which is f of three and i just have

three one so this time this will be printed so let's mark it as green next you'll go back

now you can see this entire recursion is over goes back comes over here f of 2 3 again

couple of directions pick and non pick so f of 3 comma 3 two and f of three comma just a three

so this will be again the stem printed goes back comes over here

prints goes back goes back

so i can say this entire left stuff is done where you have ended up printing three one two

three one three two and three so four sub sequences have been printed and if you

realize four subsequences were printed by taking the first element now the other

four will be printed by not taking yes the other four will be printed by not taking so i can easily do it by not

taking that'll be an empty one again you can decide to take the first index f of one

comma that'll be one and again if you decide to not take it

will be f of two comma not take again if you decide to take and

to not take it'll be like f of 3 comma 1 2 and this will be f of 3 comma 1

so if i decide this is the next printing comes back goes

next printing comes back comes back

f2 so over here what can you do again you can decide to

you can decide to pick and do not pick so if you decide to pick it'll be like f of three of

two it'll be f of three of empty so this will be printed and then this will be printed so if you carefully observe the

next set of elements were also printed which is one two one

and a two and then empty so you also printed the next four so in this way you can easily print so if i

just show you the entire recursion tree this is how it looks this is how the entire recursion tree looks quite simple

and if you want the vertical order the function calls have been made yes this is how the function calls have been

made but i still highly recommend you to go back and draw the recursion tree by yourself

to understand it okay so quite simple quite simple so if i try to write it

down in the code uh can i sell i'll be taking an array so i'll just take an array you can do it by yourself three

one two and i'll keep the n as three okay and i'll say print f

i've written a print function which will print all the subsequence starts with index 0 array and then

so let's write the printf printf i can say index i can say okay i need a data structure to carry all the

subsequence let's take a data structure to carry all the subsequence which is ds okay

so probably i can just call the vector into ds and i can pass the ds over here

that's the better one okay over here you can take vector it remember it has to be passed by

reference so please please make sure you take as a reference anyway it's gonna be n okay perfect now

can i say if at the moment it reaches n or like it'll always reach and because you're moving linearly can i print the

data structure i can definitely print the data structure so please please print the data structure which is c out

of id uh this

and after that you can just give an angle just to make sure that this is not done okay and after that you can just do

a return so this is how you print it now i'll say uh take all the condition take or pick the particular

index into the subsequence correct i can say that so what i'll be like is okay if i'm

taking it i'll say data structure to push back in

java you can use arraylist and you can just given dot add pushback array of index okay so this is

what i've done i've pushed back the rf index in order to remove it's very simple you say pop back that will be

deleted and over here i can say that printf sorry extremely sorry

printf index you have done for the current index you'll move to the next you'll

take the ds you'll take the array and you'll take then and whenever you come back now it's time to try the not pick

or not take condition where you say that this

element is not added to your subsequence okay that's what you simply do

now over here what will be the case oh yeah i can say the case will be very

simple you'll be like print f you like print f index plus one the ds and the array and the end so if

you just do this and uh probably if you just run this you will see all the guys getting printed over here

see three one two three one three two one two one two and the empty one is getting printed over here so you can

also uh like ds dot size if by chance the draw size is zero you can say it's a null one so you can also print the null

something like this this will also make sure that the null is printed so if i'll keep this c the

knowledge printed at the last because not take not take not take you can also do it in the reverse order yes you can

also do it in the reverse order where you say that okay do not pick condition will be at the front

you can also do it in this way using do not pick condition is at the front so we again run it this time it will be see

first null came because not pick not pick condition was executed and then it printed that's your wish if you want to

do the pick if you want to do the non pick then it's your wish okay now coming across to the time complexity

what's the time complexity can i say for every index there are a couple of options valid for every index you're

having a couple of options right so for every index if you're having a couple of options can i say like it's like 2 over

here 2 over here 2 over here 2 over here 2 for every index you're having two

options so the time complexity is definitely 2 to the power n no doubt in this

right and into for every subsequence you're using a for

loop to print it like it's generally not n but overall you can say it's taking a time of n to print so near about 2 and

into n is the time complexity space complexity will be how much what's the auxiliary stack space so if

you look at the recursion tree it's like going from zero to one to two so the maximum number of recursions that will

wait are three if you carefully think

not more than three recursion calls will be waiting in stack space at max three because the depth of the recursion is 3

so i can say the stack space is coming out to be weak of n because the depth of the recursion that we can have at

maximum is n so i can say this is the time complexity and this becomes the space

complexity as simple as that and do i need to explain you anything else i

don't think so i think that that is pretty much it just make sure you remember this

pick and not pick for every index you decide whether to pick and not pick since uh there are two to the power n

sub sequences for a given length n size array uh thereby we got eight subsequences for the size three

array so guys i hope you have understood this entire explanation this push back pop back up add delete remove

everything just in case if you have understood every everything please please make sure you give a like to this

video you can do that right and if you're new to this channel please please do consider subscribing and yeah with

this i'll be wrapping up this video let's meet in the next one [Music]

will find a bye-bye in

Heads up!

This summary and transcript were automatically generated using AI with the Free YouTube Transcript Summary Tool by LunaNotes.

Generate a summary for free

Related Summaries

Mastering Sequence and Series: A Comprehensive Guide

Explore the fundamentals of sequences and series. Learn key concepts along with proofs and applications. Perfect for math enthusiasts!

C++ में Array Traversal और For Loop का आसान परिचय

इस वीडियो में हम C++ प्रोग्रामिंग भाषा में Array Traversal के बेसिक कॉन्सेप्ट को समझेंगे। साथ ही For Loop के उपयोग से कैसे एक Array के सभी एलिमेंट्स को एक-एक करके एक्सेस और प्रिंट किया जाता है, इसे विस्तार से जानेंगे।

Mastering Two Pointer & Sliding Window Techniques in DSA Interviews

This video introduces the fundamental patterns of the two pointer and sliding window algorithms from the A2Z DSA course, focusing on problem-solving strategies to maximize efficiency in coding interviews. It covers four main problem types along with reusable templates, enabling learners to understand and implement optimal solutions to common interview challenges.

Understanding Data Structures Through C Language: A Comprehensive Guide

This video introduces the concept of data structures using the C programming language, explaining the importance of algorithms in structuring information. It covers various types of data structures, including linear and nonlinear types, and emphasizes the significance of arrays, stacks, queues, and linked lists in effective data storage and processing.

Comprehensive C++ Basics and Interview Prep with Striver's Resources

This video offers an in-depth introduction to C++ fundamentals, covering essential programming concepts like data types, conditional statements, loops, arrays, strings, and functions. Leveraging Striver's well-structured interview preparation sheets and courses, beginners and intermediates can build strong coding skills tailored for technical interviews. Practical coding demonstrations and tips enhance understanding and application.