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

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program that takes as input a number n in and returns all the strings with n matched pairs of parens.
Examples:
n = 1
[ "()" ]
n = 2
[ "(())", "()()" ]
n = 3
[ "((()))","(()())","(())()","()(())","()()()" ]
Approach 1 (Brute Force Then Validate)
Generate all (2 ^ (2n)) possible parenthese strings and then validate each for being balanced.
If n = 2 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.
This lower bounds our time complexity.
Even if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(2k, k) strings to consider for validation.
Approach 2 (Directed Backtracking)
The 3 Keys To Backtracking
Our Choice:
Whether we place a left or right paren at a certain decision point in our recursion.
Our Constraints:
We can't place a right paren unless we have left parens to match against.
Our Goal:
Place all k left and all k right parens.
The Key
At each point of constructing the string of length 2k we make a choice.
We can place a "(" and recurse or we can place a ")" and recurse.
But we can't just do that placement, we need 2 critical pieces of information.
The amount of left parens left to place.
The amount of right parens left to place.
We have 2 critical rules at each placement step.
We can place a left parentheses if we have more than 0 left to place.
We can only place a right parentheses if there are left parentheses that we can match against.
We know this is the case when we have less left parentheses to place than right parentheses to place.
Once we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.6 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

[@BackToBackSWE]

Table of Contents: Introduction: Discussing The Past 0:00 - 0:33 Talking About The Implications Of Today's Video 0:33 - 1:08 The Problem Introduction 1:08 - 3:00 The 3 Keys To Backtracking (As Always) 3:00 - 5:01 Tracing The Recursion Tree: Watch The States 5:01 - 10:16 Time Complexity 10:16 - 10:48 Space Complexity 10:48 - 11:19 Subscribe To Us Plz 11:19 - 11:41 The code is in the description. Fully commented for teaching purposes and understanding.

[@faizannasimhyder9011]

Where is the code in the description?

[@mohammedshahraazhussain1759]

When he speaks, It feels like he is about to get inside my brain.

[@BackToBackSWE]

hahahahahahahaha, ok

[@user-uq1nr5uh6l]

Your voice is 66666 in chineses.

[@BackToBackSWE]

@@user-uq1nr5uh6l what

[@gaoyukuan]

@@BackToBackSWE "Six" pronounces the same as "溜", which means smooth or something is going really smoothly. It's often used as a compliment to say somebody or something is great (with the "smooth" feeling haha). Also, 5 * 6 means 5 times smooth.

[@joon-tech]

this just made my day hahah

[@theFifthMountain123]

You are an awesome teacher. Please keep making these videos.

[@BackToBackSWE]

Thanks. That means a lot. And I will. As long as I can maintain my energy levels high this is my dedication.

[@redherring27]

0:08 Another day another boring question to cover. 1:08 Aoolrite so today we have a fascinating question.

[@BackToBackSWE]

hahahaha sorry older video so I was goofier, no one was watching

[@user-gz7fh8vo6e]

What you said in the beginning resonated a lot with my experiences. Most videos out there explaining these solutions don't dive into the intuition behind making certain logical leaps for coming up with the solution, which is probably the crux of the difficulty. Keep up the great work.

[@BackToBackSWE]

thanks, hey

[@sean721888]

“This is the understanding I want you to understand!” Such a awesome video

[@BackToBackSWE]

thanks - vintage video...from the origin days

[@1328237]

Dude, I seriously cannot believe how much I struggled with this problem until I saw your thinking behind it. I typed up a solution in less than 5 mins. You are seriously a beast. Bless your soul man.

[@hackytech7494]

You are the best teacher on entire KZbin platform. No one have explained any problem in such an expressive way [ The way you teach ]. Thanks for your tutorials. Please don't stop teaching.

[@stark.aritra]

Keep making these videos brother, I looked at so many different people's explanations. But none explains so smoothly and deeply like yours. Keep up the good work, thanks.

[@fudgemelons]

Thanks! Struggled on this problem for a bit, but after 5 minutes of the video I was able to come up with the right answer.

[@BackToBackSWE]

AWESOME! Go get em'

[@3darpan]

You have a whole other ability to make concepts clear. Thanks man!

[@mosesindecks]

I love your videos man. They are the greatest thing to have happened on KZbin since 30 Seconds to Mars.

[@BackToBackSWE]

hahahahaha

[@cool2suck]

I've watched countless algorithm explanation videos.. yours are by far my favorite!! I can actually understand the how & why to the approach instead of just learning this is what you do. Thank youuu

[@BackToBackSWE]

Sure, tis' no problem

[@jose.dances]

Haha, I love the intro. Thanks for everything you do, Ben. I have a harder time learning some of these concepts, so it's helpful to hear that there's other folks out there in similar boats.

[@BackToBackSWE]

Old video, my bad for the intro - and great.

[@hernabaer]

I can't believe how easily I understood the solution after I watched your video. I can't believe how easily I've written the actual code without looking any example code but only watching your video. Thank you so much!

[@BackToBackSWE]

great & sure

[@johnleonardo]

My favorite explanation yet. Very satisfying when I realized how easy this problem is.

[@BackToBackSWE]

nice

[@fracturedude]

Really great job explaining. I was having a hard time figuring out the recursion. You made it clear!

[@yujiawang8168]

Amazing explanation! The clearest video on youtube I've seen to throughout this problem, thanks a lot!

[@BackToBackSWE]

thx

[@vishwajeetmanhas_5864]

Your ability to completely explaining crux of problem is amazing.

[@coconutjuice7777777]

Thanks. Understood the solution literally within 2 mins (I had spent a decent amount of time on this before).

[@BackToBackSWE]

great

[@SR-we1vl]

I guess this is the BEST CHANNEL FOR SOFTWARE INTERVIEWS!

[@BackToBackSWE]

YES

[@phanichoragudi57]

Best explanation i've seen till now. Keep rocking!

[@BackToBackSWE]

thanks

[@stephenplautz4682]

This video, and especially the 3 keys to backtracking problems were incredibly helpful for me. I have gotten so mich better at spotting and applying backtracking to problems by applying them 😄

[@sridharchaitanyagudur7462]

You have no idea what you are doing to my brain, you are making my neurons communicate at light speed. Thanks a lot. !

[@Suyashmehra0]

You know what man , you are the best teacher for backtracking out here .. keep up the good work mate ..

[@BackToBackSWE]

thanks a lot

[@flacco8985]

Extremely well explained. I was able to code it myself after watching the video, thanks!

[@BackToBackSWE]

NO WAY! THAT IS AWESOME!!! That was literally my mindset going into this video. Funny you said that. You see now? The key is knowing our choice. Once we know our choice we CONSTRAIN that choice. And then as long as we define our goal correctly we will catch all answers at the bottom of the recursion in the base cases. Thanks for commenting! This is great to hear and makes me happy as a teacher.

[@chiragkushwaha546]

Exactly no one has explained these problems like you do , nice work keep it up.

[@BackToBackSWE]

ye, will do

[@frankchen9264]

You are really awesome! I used to think about this question about an hour but I have no idea about that. But after listening to your video, I began more clear about that.

[@BackToBackSWE]

Yeah, I didn't solve this when I got it first.

[@Endlessvoidsutidos]

love the vid btw i was recommended to this channel by friends who said it was the best channel for software engineer interview training videos killing the game son

[@BackToBackSWE]

thx

[@ekejma]

He is so relatable... if I had an instructor like him in school it would have been so much easier.

[@richardli9514]

"How do I even solve this under pressure?"--my number 1 question all the time on leetcode

[@juliolopezmontalvo]

I've seen a lot of explanations about this problem but this is so far the best explanations I've seen about using backtracking, thanks!

[@BackToBackSWE]

great to hear and sure

[@karthiklv29]

You Sir are an amazing teacher, didnt even need to see the code, your explanation is gold.

[@grantherman1971]

dude this is literally the type of explaination I have looked for. So many other videos just gave a soloution and didnt really explain wtf was happenig. You are wonderful

[@BackToBackSWE]

Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/

[@nsivaramprasad]

Greatly explaned !! Problem understanding is simplified and it is lot better than going through the code for understanding !!

[@BackToBackSWE]

ye

[@ElGalloUltimo]

You are damn right about there being no videos that explain it like you do. I think the way you do and you explain it the way I think. So thank you for doing these videos. The way you cut yourself off and end the videos abruptly cracks me up btw 😂

[@BackToBackSWE]

Yeah I was geekin back in the day, the me that exists now is not the same as the 80 or so Ben's you see on your screen.

[@AllanPichardo]

Thank you so much for explaining this. Very intuitive. Also I'm glad the focus wasn't all on the code, more on the concept.

[@BackToBackSWE]

sure and yeah

[@Kushagra_21]

this is by far one of ur best video in recurssion problrms. Thanks a lotttt

[@BackToBackSWE]

I agrre minus having no mic

[@sidagarwal43]

It's only because of your videos I have been able to improve my leetcode rank. Your videos are simple and informative, please dont stop this great work ever. Love from India.

[@BackToBackSWE]

great and ok and wassup

[@code_yoda1928]

You are a gem of a person for making our lives easier.You are god sent really

[@BackToBackSWE]

thanks

[@mirceskiandrej]

Hated this problem but this is the best explanation on KZbin about how to solve it. Thank you.

[@BackToBackSWE]

Glad to be able to help. You should try our 5 day free mini course for some awesome content - backtobackswe.com/

[@muthaiahpalaniappan8009]

I can able to use this pattern for various problems. Thank you so much. Today I came across a staircase problem. I used the same idea and it worked. Thank you so much 😍 Golden words ***1. Options 2. Constraints 3. Goal***

[@mauricegoldberg7458]

Extremely well explained. Really helped this problem finally click for me. Thank you very much!

[@BackToBackSWE]

great.

[@yanxichen4236]

Thank you for making these videos! You explain the concepts and your thought process very well. Please keep up the great work! Looking forward to learning more from you :)

[@BackToBackSWE]

Thanks, and yeah...it is so tiring. I'm editing a video right now and I'm so tired. It's a lot of work.

[@yanxichen4236]

Back To Back SWE oh no... Well, I for one am glad you’re making more videos, but please do it at a sustainable pace! Burnout is no fun - I’ve no doubt your channel is going to be one of the biggest swe prep channels one day, but there’s no hurry in getting there! And thank you thank you for your hard work :)

[@BackToBackSWE]

@@yanxichen4236 haha thanks

[@waliiut08]

Every time I get stuck in a tough problem like that or cannot think to code properly (most of the time it is so depressing), I just see your explanation for that problem. After seeing your explanation I really feel that I have to think the way you think to solve any problem. Your videos help me to understand the problem and to get the motivation to think deep like a true engineer. Please keep up your good works. Best of luck and thanks a lot.

[@BackToBackSWE]

Nice! thanks, all this interviewing stuff doesn't really map to real engineering but it is an exercise in thought

[@katyasadovnycha6670]

You cracked me up lol.. ''another day, another really boring question to cover'! Can't agree more :D

[@BackToBackSWE]

my bad - old video I messed around more

[@ujjvalsharma5055]

Hey man wonderful explanation there. One of the best on the internet. Keep it up : ). I hope you post more videos

[@BackToBackSWE]

thanks

[@adityasoni1207]

ou are an awesome teacher. Please keep making these videos. Thanks a lot!

[@BryanAndradeNYC]

I've watched a few of your videos. I like the way you explain CS concepts clearly. Subscribed and thank you for taking the time to make this.

[@BackToBackSWE]

Sure, it is nothing. Just a part of my mission. I'd really appreciate it if you shared content you like or the channel on reddits like r/cscareerquestions. They keep denying me a post and I think these videos would help so many.

[@shantanunair]

@@BackToBackSWE Wow sucks that they don't let you post. But I can see why. I'll try and spread the word on r/cscareerquestions and on hackernews.

[@poojachi]

Best explanation! looking forward for more videos!

[@BackToBackSWE]

yep!

[@davngo]

Thank you! This video helped me gain a better understanding of recursion.

[@BackToBackSWE]

nice -Ben

[@hbhavsi]

Bless you dude! Great explanation and very well documented solution.

[@BackToBackSWE]

Thanks, wassup

[@osamayounus4867]

This explains everything so well. Thank you

[@harini3191]

U made these concepts very clear and your teaching method is really good ! thanks

[@BackToBackSWE]

sure

[@ferneutron]

Really good content! I've been struguling with Batctracking/Recursion and the way how you explain is super clear and understanable. Thanks a lot!

[@BackToBackSWE]

glad to help!

[@seungjinkim8860]

Thank you! Drawing out the recursion tree is key to understanding this problem for me.

[@BackToBackSWE]

sure

[@mohamedabdul633]

Wow you are genius man, I wish found this video before. I was depressed that I could not even solve this problem, this video helped me to break down the problem.

[@BackToBackSWE]

nice, glad to hear

[@rahul10anand1]

Crystal clear, thanks, Ben!

[@BackToBackSWE]

sure.

[@praptitrivedi7449]

Keep up the good work! Got the intuition quite well.

[@BackToBackSWE]

good

[@idundidit]

man... I finally understand this. Thanks so much for putting this explanation together.

[@BackToBackSWE]

sure thanks for watching

[@hs9687]

definitely the best explanation for this question. thanks a lot!

[@BackToBackSWE]

sure

[@oludarevictor4611]

Dude, you are amazing! I wish I found your channel before now

[@BackToBackSWE]

No ur amazing

[@vinayak186f3]

I could code it by myself , all thanks to you sir .

[@fathimasifasyedmusthafa9410]

u are a great teacher , pls continue teaching. Ur voice first of all makes it interesting which every teacher needs.:) awesome !!

[@darshansimha2166]

Thank you 🙏 . Really helped me visualize the backtracking.

[@annarzheutskaya5301]

A very good explanation! Great job.Looking forward to new videos.

[@BackToBackSWE]

Glad you liked it!

[@avoo1d]

My God, I just love this explanation, Thank you very very much, because of your explanation I do not have to see already written code and did it myself with recur.

[@BackToBackSWE]

nice thanks

[@CodeSuccessChronicle]

It is indeed the best channel for s/w engineering students :D

[@aanyaaryancoolgamers2013]

Awesome explanation. You are making our lives so easy. Your channel gonna rock!!!!!!!!!!!!!!!!

[@BackToBackSWE]

thanks. just trying.

[@palashkamble2325]

Dude, when you started with top down approach and said there can be two decisions to make at each node, I was like damn it is that easy to solve. Why couldn't I just come up with this approach? oh wait, I know, practice is all I need. Thanks btw :)

[@BackToBackSWE]

great and thanks.

[@harinijeyaraman8789]

YOU ARE AMAZING !!! Thanks a ton for this video

[@BackToBackSWE]

sure!

[@linnaqiao6076]

Really great and clear explanation! Thanks!

[@BackToBackSWE]

sure

[@chetanpatteparapu7600]

Thanks for your great explanation. I always struggle with Cominbators topic.

[@bhavyachawla7176]

This video and that damn neatly commented code blew my mind . Thanks a lot !!!!!!! :D

[@BackToBackSWE]

sure

[@mrunaldave6781]

Dude you're the best. Thank you very much.

[@kuralamuthankathirvelan]

No comments , Simply Awesome 👌.

[@BackToBackSWE]

thanks

[@charliel7041]

that is so helpful for me to understand! amazing! thx so much

[@BackToBackSWE]

sure

[@nazmussakib5983]

Thank you so much for the clear explanation! coded it after watching only 6 minutes of the video...:)

[@BackToBackSWE]

Excellent. Keep practicing. Keep getting better. Tell me of any offers you get one day! :)

[@nazmussakib5983]

@@BackToBackSWE of course. I will!

[@cryptojeff3993]

Best Explanation for this problem!

[@marksargent3209]

The best I've seen so far.

[@BackToBackSWE]

haha thanks

[@darod6098]

Keep going this good work man, you're the best. The only thing that I would love is having more videos, nothing else. (Especially about Graphs, Trees and Bit Manipulation)

[@darod6098]

Just to say: Your code could be better in terms of performance if parenStringInProcess would be an StringBuilder instead of an String, and then just convert to String before adding it to the list, right? Because in this way we're having problems of performance with the immutability of the String class

[@BackToBackSWE]

@@darod6098 More videos are coming. And yes, I'm aware of this inefficiency, if you want you can fix it up and open a PR. I'd gladly merge it in.

[@darod6098]

@@BackToBackSWE PR opened! :)

[@BackToBackSWE]

nice

[@neesargmistry2071]

bro, keep making me understand how you understand it because I understand it the best the way you understand it :)

[@BackToBackSWE]

Thank you, I will

[@anuragkothare6181]

Great Explanation. Crystal Clear.

[@BackToBackSWE]

thanks.

[@ninghaohe5084]

you are a legend BRO !!!

[@2280281]

Simply Amazing!!! You made my Day

[@explorewithswetha.]

Very clear explanations! Thank you.

[@BackToBackSWE]

sure

[@mausami16mau]

you made it very simple and easy to understand, thanks.

[@BackToBackSWE]

thx

[@karnifazil]

Awesome explanation! So nicely explained backtracking.

[@BackToBackSWE]

thx

[@dexterellis7973]

Thank you for breaking this down.

[@garylai5174]

Wow man thanks so much! This explanation is beautiful :)

[@BackToBackSWE]

sure

[@kuralamuthankathirvelan]

Keep on posting videos !

[@BackToBackSWE]

k, prolly won't be technical though for a bit

[@wh264]

Super helpful, really help me grok the concept better without completely giving out the answer

[@BackToBackSWE]

great

[@nishadkumar7322]

Finally, someone who did it right! Thanks @Benyam Ephrem.

[@BackToBackSWE]

sure

[@tesfayhisheteka8158]

I really like your videos and I can say I have learned so much from your videos, Thank you for your great videos!! Can I ask where I can find the link to the code? I couldn't find it on the description!

[@sauravkumarjha2838]

very clearly explained. thanks a lot.

[@BackToBackSWE]

thanks

[@ridhisood4951]

I was so confused with the solution of this problem. But now finally understood the backtracked solution.. thanks for making this video..

[@BackToBackSWE]

Nice! happy

[@MostafaAliMansour]

Dude u r really awesome, keep up the great work 🤗

[@BackToBackSWE]

thanks, i try

[@kadamdeepali2011]

Superb explaination.. Thank you so much. I was struggling to solve this problem. After looking at video . It got cleared.

[@BackToBackSWE]

sure

[@Justin-yq8hf]

Thanks for pointing out the time complexity

[@ijustdey]

Absolutely Ingenious