Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)
HTML-код
- Опубликовано: 2 окт 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 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.
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.
Where is the code in the description?
When he speaks, It feels like he is about to get inside my brain.
hahahahahahahaha, ok
Your voice is 66666 in chineses.
@@夏天-y3j what
@@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.
this just made my day hahah
You are the best teacher on entire RUclips 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.
0:08 Another day another boring question to cover.
1:08 Aoolrite so today we have a fascinating question.
hahahaha sorry older video so I was goofier, no one was watching
Your ability to completely explaining crux of problem is amazing.
You are an awesome teacher. Please keep making these videos.
Thanks. That means a lot. And I will. As long as I can maintain my energy levels high this is my dedication.
Hated this problem but this is the best explanation on RUclips about how to solve it. Thank you.
Glad to be able to help. You should try our 5 day free mini course for some awesome content - backtobackswe.com/
Thanks. Understood the solution literally within 2 mins (I had spent a decent amount of time on this before).
great
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.
thanks, hey
Greatly explaned !! Problem understanding is simplified and it is lot better than going through the code for understanding !!
ye
this is by far one of ur best video in recurssion problrms. Thanks a lotttt
I agrre minus having no mic
You Sir are an amazing teacher, didnt even need to see the code, your explanation is gold.
Super helpful, really help me grok the concept better without completely giving out the answer
great
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.
sure and yeah
Amazing explanation! The clearest video on youtube I've seen to throughout this problem, thanks a lot!
thx
“This is the understanding I want you to understand!”
Such a awesome video
thanks - vintage video...from the origin days
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.
AWESOME! Go get em'
Really great job explaining. I was having a hard time figuring out the recursion. You made it clear!
You cracked me up lol.. ''another day, another really boring question to cover'! Can't agree more :D
my bad - old video I messed around more
Awesome explanation. You are making our lives so easy. Your channel gonna rock!!!!!!!!!!!!!!!!
thanks. just trying.
"How do I even solve this under pressure?"--my number 1 question all the time on leetcode
Superb explaination.. Thank you so much. I was struggling to solve this problem. After looking at video . It got cleared.
sure
Awesome. After listening to this one, I was able to write code in less than 5 min and passed all the LC testcases. The constraints part is what is really needed and the code just flows.
nice!
Dude, you are amazing! I wish I found your channel before now
No ur amazing
Your the best teacher ... Keep up the work!! please do post lots of videos like this!!.. Thanks for your efforts..
ok, coming right up
Great Explanation. Crystal Clear.
thanks.
Finally, someone who did it right! Thanks @Benyam Ephrem.
sure
This video needs a revisit. The basics were explained well, but I feel like we could explain more like completing the right side of the tree and also does this have a dp table implementation? also the TC proof for this would be great as well.
yeah, I agree
Best explanation i've seen till now. Keep rocking!
thanks
Perfect explanation. Took me 4 minutes to write Accepted code on leetcode after 6 minutes of your video. Amazing job
thanks
This video and that damn neatly commented code blew my mind . Thanks a lot !!!!!!! :D
sure
I think the below time complexitiy explanation would be enough.
Time Complexity :
Tree height = 2N
How many choices each node level? 2 choices
T(n) = O(2^2n)
We have a global result bag. would be the number of leaf nodes and length of the result append: 2n
Finally :
T(n) = O(2^2n) x O(2^n) = O(n.4^n)
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 :)
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.
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 :)
@@yanxichen4236 haha thanks
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!
great & sure
Got it yesterday in a interview, screwed up completely 😆...if you haven't seen this stuff before no way you'll come up with an answer
Absolutely Ingenious
Says he's not a teacher and then goes on to explain these concepts better than any professor I've ever had lmao
ye
I guess this is the BEST CHANNEL FOR SOFTWARE INTERVIEWS!
YES
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.
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!
best explanation I've ever seen!!
thx
The best I've seen so far.
haha thanks
If you can present the code and explain i"d appreciate it
Great explanation btw
Best explanation! looking forward for more videos!
yep!
kept on saying this is a breadth-first and this is not how recursion does it and then, in the end, didn't explain how the program actually does it in depth-first.
ok
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
Sure, tis' no problem
Thanks. You are the best.
Hi Benyam Ephrem,
Firstly the explanation is very clear and understandable even in such a short video. Second, I want to point out that there are atmost 2n stack frames and each stack frame stores a string which is of max length 2n. So Space complexity is O(2n*2n) i.e O(n^2) . Thanks!
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
Hi
Thanks for the videos.
Where do you exactly find the code in the description?
Thanks
The repository is deprecated - we only maintain backtobackswe.com now.
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 :)
great and thanks.
You, sir should consider a career as a teacher full time. Jamazing
Indeed I am pondering such a choice.
My favorite explanation yet. Very satisfying when I realized how easy this problem is.
nice
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.
great and ok and wassup
I have a question.
I translated your code to Python and it works fine but one thing I noticed and that I wasn't able to figure out for the life of me is why do I get duplicated combinations by the following modification:
if o > 0:
o -= 1
result += '('
generate_parentheses(o, c, result, results_list)
if c > o:
c -= 1
result += ')'
generate_parentheses(o, c, result, results_list)
Instead of adding to the string and subtracting from the number of parentheses while passing them as arguments, I do so before invoking the method. The result is that I get duplicate combinations.
Why is that? Shouldn't these two have the same result?
Amazing explanation of the core concept btw.
Nevermind. Figured it out. I'm not supposed to change the values of the result and parentheses count variables in place.
nice
Thanks for your great explanation. I always struggle with Cominbators topic.
Awesome videos - I appreciate the effort and energy you put into these - very clear/concise explanations.
One question, though - could you explain how this is really backtracking? Aren't we just eliminating potential recursive branches based on the constraints? My understanding was that backtracking includes "undoing" our choice at some point. Or does the elimination of a potential solution qualify the algorithm as backtracking.
thx - this is just implementing the constraints with recursion, backtracking involves choices that could be on an infeasible path. We prune those out anyway with our constraints so it is just recursion.
Thought it was funny, mans was like if you get asked the time complexity you're taking the L
hahahahaha - yeah. You'd have to do actual math
@@BackToBackSWE Might be blind, but couldn't find the code in the description, if you kept it somewhere else
it gets more confusing because u don't explain it in the recursion manner please do it the recursion way :)
ok
dont be too narrow.It can be done in many ways
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!
great to hear and sure
your teaching is awesome...plz can you tell me where the code is ??
The repository is deprecated - we only maintain backtobackswe.com.
Where is the code??
YOU ARE AMAZING !!! Thanks a ton for this video
sure!
you are a good teacher, tbh, I give up most of videos speak in Chinese.
haha
Great navigation of how to approach the solution using the backtracking strategy. While one thing is my mind is when we get hit by a problem like this one, there is actually another possible approach in my mind: Can we deduct the solution to n based on the solution to n-1. And an interesting question is how do we make the decision in the very beginning to choose between the backtracking approach and the induct approach (induct solution from n-1 to n). BTW thank you very much for all your videos !
thanks and sure
very clear thanks
hello sir,
plz
make tutorial on
Hu & Shing's matrix chain multiplication in O(nlogn) and catalan number
ok
Can we say time complexity is O(3^n) ?
I could derive this :
n=1
1 string
n=2
2 strings = 1 + 1 = 1 + 3^0
n=3
5 strings = 2 + 3 = 2 + 3^1 = 1 + 3^0 + 3^1
n=4
14 strings = 5 + 9 = 5 + 3^2 = 1 + 3^0 + 3^1 + 3^2
n=5
42 strings = 14 + 28 = 14 + 3^3 + 1 = 1 + 3^0 + 3^1 + 3^2 + 3^3 + 1
= 1 + 1 + (3^n-1 - 1) / 2
n=6
132 strings = 42 + 90 = 42 + 3^4 + 9 = 1 + 3^0 + 3^1 + 3^2 + 3^3 + 1 + 3^4 + 9
= 10 + 1 + (3^n-1 - 1) / 2
n=7
429 strings = 132 + 297 = 132 + 3^5 + 54 = 1 + 3^0 + 3^1 + 3^2 + 3^3 + 1 + 3^4 + 9 + 3^5 + 54
= 64 + 1 + (3^n-1 - 1) / 2
Above are # of strings for different values of n = O(3^n)
this is not time complexity
Time complexity is about # of recursive function calls
for n = x
recursion tree has x levels
# of calls at each level is as above (because strings always belong to the final level for a given value of n)
Hence T(n) = Σ3^k k=[1,n] = -1 + (3^n+1 - 1) / 2 = O(3^n)
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
thx
Thank you! Drawing out the recursion tree is key to understanding this problem for me.
sure
Extremely well explained. I was able to code it myself after watching the video, thanks!
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.
1. why we are ONLY able to put the new left/right Parentheses at the rightest side every time?
2. According to the above limitation, why we could say the final level leafs are the answer?
Thanks 🙇♂
Thanks for the explanation. But I really doubt about the time complexity of your approach. It will definitely be close to exponential as we are going through all states. Great approach. I feel we can achieve O(n) only through finding catalan number.
where is code? i dont see in description
very clearly explained. thanks a lot.
thanks
thanks man awesome
thanks
Hey thanks for the easy explaIation. But I cant see the code in the description. Is it removed?
I don't understand how this is backtracking, I didn't see any backtracking going on in the diagram (compared to other backtracking problems)
i feel writing psuedocode and actual code is very different. If you could include code as well it would be great. like how to put these parenthesis in a method that is called recursively
ok
why there are (2 ^ (2n)) possible parenthese strings...I know where 2n comes from, but what about another 2?
Best Explanation!! Just one query, why is (open < max) as a condition and why not (open < 0)? Please ans
Thanks and I don't remember? I can't allocate the time to reread the code because of the mass of comments
Back To Back SWE: Awesome video..... could you please also elaborate about the time complexity?
u are a great teacher , pls continue teaching. Ur voice first of all makes it interesting which every teacher needs.:) awesome !!
Played the video in 2X. What a great rap! Even better than Eminem. Thanks for the awesome video.
what lol
Thanks for video Ben, really good explanation. But, I still have an open question about time and space complexity. I read an article with solution (on Leetcode, task 22), and that final formula makes me madness. In discussion of this task, some people say, space and time is exponential. Is that correct?
I have no idea, I don't remember how the math was done for this one
Awesome explanation +1 Sub!
thx.
i love how you just skip the time complexity altogether with a blunt reason lol. great video!
not sure if this is bad or good but k
No comments , Simply Awesome 👌.
thanks
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.
Nice! thanks, all this interviewing stuff doesn't really map to real engineering but it is an exercise in thought
I love your videos, they help me alot.
However when I see the question on leetcode or any other coding site, I can't even figure out which technique to use. Even if I spend hours, I can't really figure out which technique to use & how to solve the given problem.
I've studied the DS & algos but I still can't come to a solution. I'm at a stage that I don't know what to do. I feel that I'm just not good enough. Did you face the same dilemma?
Can you please make a video on figuring out which type of algorithm can potentially be used based on keywords in a question? That'd be really really helpful!
yes but maybe not now due to time constraints
I was so confused with the solution of this problem. But now finally understood the backtracked solution.. thanks for making this video..
Nice! happy
Tqq so much for these videos..U really explain the concept veryvery well!!
Thanks for your great video! Can I ask a stupid question😂, how can I find the solution for this question? I noticed that you said "the code is in the description for this problem ". I just don't know where is the description and that corresponding link? Thank you so much!
The repository is deprecated - we only maintain backtobackswe.com now.
I get it! 😊
Where is the code in description? Can't find it
We only maintain our code on backtobackswe.com
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 😄
Thanks for the videos. Where do you exactly find the code in the description?
The repository is deprecated - we only maintain backtobackswe.com now.
I don't see your code? Have you removed it?
We only maintain code on backtobackswe.com.
You are the BEST
hahahahaha...ummmm...working on it
Great Job.... Wouldn't the time complexity be upper bound by O(2^n)?.....50% of the time, two choice are made and the other times a single choice is made.
That'd be a rough upper bound, yes, but it can be more exact because 2 forks are not always made at every node because the tree prunes itself
@@BackToBackSWE You are also correct. However, during an interview it better then I don't know (?).
Today we are going to make it very easy!!!
great
that is so helpful for me to understand! amazing! thx so much
sure