Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)

Key Takeaways

[Music] all right another day another really boring question to cover so the thing is I don't even think that I'm that good of a teacher I'm not even that passionate about these questions but the thing is I never found anyone that really could explain them the way I wish I was learning them like the way I wish my the way I wish I could have received to be learning the way my brain is slowly creeping into these concepts I think today's video is kind of going to be like that today's video is about the N matched parens problem this problem is really key in understanding how recursion can express our decisions and how constraints can change how a recursion happens through our recursion tree before I even knew a backtracking was I tried to solve this question with like a group of friends we like sat down or like yeah we're gonna do this I literally sat there a half-hour to an hour and I did not know what to do and if you don't know the principles of recursion and how it adapts this problem this problem can be very easy or it can be very difficult today we are going to make it very easy all right so today we have a fascinating question that really expresses the fundamentals of recursion it is called the and matched parentheses problem whenever you want to call it so our input is a number it is M it is the number of open brackets that we need to generate all of our parentheses of certain amount of parentheses with an open brackets and we're going to have and closed brackets so if n is one you see we have one open and then one closed bam that is one if n is two then we have two open brackets and then this but then there's another possibility we have a 1 open bracket close it 1 open bracket closes and then when n is 3 then we have even more possibilities so the possibilities scale very exponential we have 3 opens 3 closes let me do two opens 1 close 1 open 2 closes and then you get the picture so this problem is very confusing where's the pattern how do I understand this how do I make sense of this how do I even solve this under so I want to make this very clear for you and I want you to notice the key things that matter this is backtracking we will be expressing a ton of decisions and of course whenever we have backtracking problems the brute force will be like an exponential complete search we generate all these strings with an parentheses and then we validate them and the valid ones we keep okay that's brute force we're not doing that we're going to be using backtracking for this problem we are going to be making decisions based on three key things the three keys to recursion that I magically invented someday we have our choice our constraints and our goal so let's look at the three keys to backtracking how they influence our recursion and how they influence how we craft our functions if you have not seen the countless other backtracking videos I've made these are the three keys to backtracking that we must keep in mind solving these problems this makes it very simple it takes a complex problem with a wide decision space and narrows it down to the choices that we make at each stack frame of our recursion every stack frame has a state and that state dictates how we act so our choice our choice is going to be at each stage do I open a bracket or do I close a bracket our constraints I cannot open more brackets than the brackets I'm given if n is 3 I cannot have 4 open brackets and maximum I can have 3 open brackets I can't have one open 1 open 1 open and then close close close that is the maximum open brackets I can have the constraint on my right bracket is going to be I cannot close a bracket that has not been opened if I have 0 left brackets I cannot suddenly just put a right bracket I can't have a right bracket as my first bracket that will have a unbalanced parenthesis string the key is our constraints we can't place more or less than N and we cannot place a right bracket unless we have a left bracket for that right bracket to balance our goal our goal is to place n times 2 characters and is going to be opening brackets we can have any times 2 if n is 3 then the length of my final strings are going to be length 6 so if I have three open left's then I'm inevitably gonna have three closing rights so and times two is our goal once we have done n times two placements we are finished we print or at that string to our array and then we recurse we allow our callers to express more of their states and create more possibilities that is the key to this problem now let's do a walk through keeping in mind these constraints and see how simple it becomes when we keep these constraints in mind through our recursion so now I starts my recurring the state of the top-level frame is I have three open brackets I can place and I have three closed brackets I can place from the first position can I place a left bracket yes I can can I place a closing bracket no I cannot because I have not opened any brackets if I had placed a left bracket this amount of open brackets would be less than the amount of writes brackets that I have left to place so now we place a left bracket so we have a lost one left bracket that we have to place we have three to place now we have two left and what our string looks like now is this alright and now from here can I do an open bracket yes I can I have open brackets to use can I do a closing bracket yes I can the amount of left brackets are less than the amount of right brackets left to use there is a left bracket I can close I have that choice I can make two good choices here open a bracket or closed let's make both of them and again this is not how the recursion would proceeded go into depth first manner we're just doing this for example sake and so now you see we used a left bracket we're down here we have one less left bracket to use but we still have three right brackets left to use and now we have not used a left bracket we still have two but we just used a right bracket we close and guess what from this position ality there's no way we can use a right racket why we've already closed our last racket do you see the left is not less than the right brackets I've left so we know that's gonna happen there so let's continue on from these positions so can I open a left bracket yes I can I have left brackets left can I open up a right bracket of course I can I have less left brackets than right brackets less brackets left to be exact and I am able to put a closing bracket so let's express both decisions and now notice this is our new positionality again we're going breadth-first like this this is not how recursion would do it it would go depth-first but anyway so we use the left bracket 1 we subtract 1 from 1 now we have no left brackets to use all we can use is right brackets that's fine we have three left brackets to close the way we get the amount of brackets so close we do write brackets that we have left - left brackets so there's three left brackets to close here that's fine we can place right brackets there so here we see our left bracket amount stayed the same but notice that our right bracket amount reduced we've made a closing from this position can I place a left bracket yes I can there's a 1 right there can I place a right bracket yes I can there are left to practice to close two minus one is one there's one Open bracket here that I can close and we notice that is true so here can I place a left of course there's a one right there I still can do that from this state in my recursion can I place a right bracket yes I can there's one less than two so now from this position I can express more things so let's express even more possibilities and do you see now as we're getting lower and lower in this recursive tree we are approaching the answer we are approaching the output that we desire again code will not do a breadth-first like this is going to do a depth first but you can see how these are the base cases that craft our answers and from here these positionality x' we can make another step here what can we do we see 0 we cannot place the left but we can place our rights because the amount of left's we have left to use is less than the of Rights we have left to use therefore there are two left's that we need to close from this position we're going to close a right and then from that position we're done close or right from this position what can I do I can open a left but I cannot open a right why there are zero left brackets unbalanced at this position I cannot do that I cannot place a right from here I cannot place a left I have zero left's left to place I can place a right though and I from there I will place another right because I have zero that's left to place from this position but I have two rights left's place if the rights will just close everything off from here what can I do I can place one left that is fine I have a left left to place but I cannot place a right why the reason is there's no left's left to close we need to open a bracket before we can close so from this position there's going to be one opening bracket but we cannot do a closing bracket so this is the intuition this is the understanding I want you to understand I want you to know from every position we have a state and every one of those states dictates how we continue in our recursion in will dictate how we approach our answer if we finish this tree off we would have our answers that's how the code would be by the way the code is in the description for this problem but this is the intuition behind this problem we want to know how many opens we have left to use how many closes and how do those constrain each other so that is the key to this problem all right so far our time and space complexities for this problem and is our input it is the amount of the left brackets we can open or it's the amount of n matched parentheses so if n is 3 our strings are going to be length of 6 because for every left that we open we need a right to close it so then we would have 3 times 2 we got 6 as a length of n is 3 so for the time complexity the time complexity is actually pretty involved in an interview you would definitely not have to deduce the time complexity exactly but I'll leave that up to you because I would probably explain that wrong for the space complexity so if n is 3 at maximum our call stack is going to go a depth of 6 because we are going to need to make six placements for the length of the string so the length of the string is going to be two times n so that yields this and then it just becomes o n we're going to scale in a linear fashion as the end gets arbitrarily large so that is how the space complexity works and the time complexity you would probably not have to perform in the interview if you did that would be an unfortunate because it is fairly rigorous so that's all for this video if this explanation was clear subscribe to the channel and like this video these videos are to help software engineers prepare for the interview I want to this channel to become the best channel for software engineering videos and to teach these subjects as clear as possible so that people can understand them easily so that is [Music]