Think this problem is significantly easier to conceptualize without a stack. You can just use a path variable in the backtrack function and for the conditions where we call backtrack, use path + "(" or path + ")" along with the updated closedN and openN counts. Using a global stack is a bit confusing IMO. def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(open_n, closed_n, path):
if open_n == closed_n == n: res.append(path) return
Thank you, I think I agree with you. Here are my iterative and recursive solutions: Iterative: class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] parentheses_stack = deque() parentheses_stack.append(("(", 1, 0)) while parentheses_stack: s, open_count, close_count = parentheses_stack.pop() if open_count < close_count or open_count > n or close_count > n: continue if open_count == n and close_count == n: res.append(s) parentheses_stack.append((s + "(", open_count + 1, close_count)) parentheses_stack.append((s + ")", open_count, close_count + 1)) return res Recursive: class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def backtrack(s, open_count, close_count): if open_count < close_count or open_count > n or close_count > n: return if open_count == n and close_count == n: res.append(s) backtrack(s + "(", open_count + 1, close_count) backtrack(s + ")", open_count, close_count + 1) backtrack("(", 1, 0) return res
Actually, it is confusing how making a change in a function call differs from changing it inside the function. If someone got it please explain to me..
I’ve been practicing leetcode for upcoming interviews and I gotta say, your explanations are just so goddamn good. Clear, concise and easy to understand. I don’t know what I would do without these videos.
You have this in the stack section of Neetcode but I think it's better in the backtracking section. As someone who is going through neetcode right now, I have reached this problem and it's great to learn but it would be better if it was in the backtracking section since I would be doing repetition on those backtracking questions at that time.
@@NeetCode It is still at stack section and this problem actually blow my mind because of it :D. I wondered how can I use stack in order to solve it but I could not figure out. It would be better to move it imho
@@NeetCode Hey it's still in the stack section, which was a bit of a brain explosion when trying to attempt this question. I look forward to retrying this question once I'm familiar with backtracking, however, as other people have suggested it would be best to move the question to the backtracking section to help out other people in future. Thanks :)
As soon as you said opening parentheses are less than the number of closing parentheses I got the answer. Finding the happy/sad paths is a really good way to begin tackling these problems.
You provide a good explanation to your solution; however, the concept that this problem is meant to focus on is not specifically the stack data structure, it's the backtracking method
I was able to come up with the same idea for solving this. But what blown me away was the implementation. I tried to use DFS using graph to solve this literally taking this idea. But the way you did with the backtracking is so efficient in terms of time and memory. Kudos man 👍
hey, while this problem contains a stack and it is under a stack section on your website I think its more about a backtracking approach. So I reckon its better to move it there. Cheers!
You offer one of the best explanations in YT. Keep up the great work! BTW in your opinion do you think most FAANG engineers could solve questions like these if they have never seen or have done something similar before?
I have always admired people who back heir solutions with the recursive tree diagram or the recursive call stack diagram. U have done just that . Thanks and Kudos 🙏🙏😀😀🔥🔥❤️❤️👍👍
for those who are wondering about the time and space complexity, lets break it down, for are essentially having 2^n calls in total, because we have 2 choices at each call, and we go n depths, so its 2^n, each time, we are building an array with n of "()", we can say that upper bound, we have about 2^n leaf call (less than this cos there's duplications and etc.). at each leaf call, we are building the ["(()).."] and append it to our res, so this add about n time for each 2^n leaf node. so runtime will be (2^n) * n, (consider n as 2n cos we have '(' and ')'), spacewise, we use backtrack, we only have 1 arr to build it, but the result will be taking 2^n * n space cos we have to store it and return it. so space and time is about the same. i feel that this question should be marked as recursion or backtracking problem rather than stack.
I came up with this solution without watching this video - def generateParenthesis(self, n: int) -> List[str]: result = [] def recursiveParenthesis(n, op = 0, cl=0, current=""): # 'op' means opening bracket count and 'cl' means closing bracket count if op>n or cl>n or cl>op: return if len(current) == 2*n: result.append(current) recursiveParenthesis(n, op+1, cl, current+"(") recursiveParenthesis(n, op, cl+1, current+")") recursiveParenthesis(n) return result Glad that the approach is almost similar.
What makes this algorithm go through all possible combinations? Why doesnt the recursion stop after the first combination [ "( ( ( ) ) )"] is added? Like it seems this algorithm would just go through adding three open parenthesis first and then three closed next and would return from the original backtrack call after its added to the result?
It's difficult to visualize because it's backtracking. Conceptually you can think of it as a DFS exploring each allowed "node" or combination. When the DFS call pops from the call stack, it tries to "explore" other "nodes". So after ( ( ( ) ) ) is added, it backtracks all the way to ( ( where it's allowed to add a ) which eventually gives us ( ( ) ( ) ). Then after it backtracks again to ( ( ) ) and we eventually find another answer.
I solved this problem but code was too complex and this really helped me out. I chose to add an extra parameter to the backtrack function to keep track of the currentSolution, it uses less memory and is a little bit faster. Thank you so muchhh
What would the time complexity of this backtracking algo be? How would u analyze the time complexity of recursive algos I find it pretty hard sometimes to do that
The reason why is because stack is a global. You have to keep the stack in sync with how the backtracking recursions are behaving. So if you tell the code that we're going to add a (, after when you're done with that backtrack, you have to remove it so the stack is consistent for the next possible recursions.
To put it simply: Each time you push the ( or ) onto the stack, you are effectively saying "Now we're branching off to all possibilities after adding a (" or the same for ")". In the tree he showed, the push onto the stack is just done for each point a node branches out to more nodes, hence we pop it off when we want to go back up the tree and down a different branch
stack keeps track of a single branch of the tree (a single value in the result array), but its being repeatedly passed down each path... need to clear it on the way back up for reuse down the next tree branch. (could also have cloned the stack before pushing onto it... or use an immutable string instead of a stack)
The confusion here might lie because of a false impression that recursive calls of many branches are executed in parallel, indeed they are not, so think about that like this - every path of a tree gets traversed till a final node ( well, leaf ) _consecutively_, though recursive nature of the code does not give such an impression. That means on every hop of this traversal we just add another element to stack , now when we go back ( traverse reversely ) on every hop we do exactly opposite - remove one element from stack , so we end up with empty stack on the top when we return from the rabbit hole of recursive calls. I still think it’d be better to avoid that complexity and just pass stack or array as a recursive procedure call parameter , this would avoid this type of question 😂
Did it slightly differently. Hope this helps def generateParenthesis(self, n: int) -> List[str]: # Create a array to store the result results = [] # Create a function to recursively form parantheses def form_parantheses(combination: str, open_parantheses: int, close_parantheses: int) -> None: # Base case, if the number of close_parantheses > open_parantheses, result is invalid or if the sum of both exceeds total if close_parantheses > open_parantheses or (open_parantheses + close_parantheses) > (n * 2): return # Second Base case, if the number of open_parantheses is equal to each other and to n * 2, we have a valid solution if open_parantheses + close_parantheses == n * 2 and open_parantheses == close_parantheses: results.append(combination) return # We have two decisions here, either we can add an open parantheses or a closed one form_parantheses(combination=combination + "(", open_parantheses=open_parantheses + 1, close_parantheses=close_parantheses) form_parantheses(combination=combination + ")", open_parantheses=open_parantheses, close_parantheses=close_parantheses + 1) form_parantheses(combination="", open_parantheses=0, close_parantheses=0) return results
I don't understand how the code produces all 5 different outputs for when the case is 3 (as example). I only understand how it does the following one: ((())), but how does it randomly generate the other solutions such as (())()???
Hey could you make the explanation of time and space complexity of the solution a separate TH-cam video chapter?. Great videos btw...I think whenever I'm just reviewing problems via your videos, just having that chapter will make it really easy for people for myself. Thanks.
Hey, did you explain about the time complexity in this video? I've watched and I didnt see... I asked chatGPT about it and explained about O((4^n)/(n^(3/2)) time
Call me pedantic but parenthese is not a word. The singular form is parenthesis. PARENTHESIS! I'd also accept "bracket". Aside from that, amazing video! 👏
What i observed was if we add two balanced paranthesis the resulting string will also be balanced. So I started with the base '( ) ' for n=1 and just added the same recursively at every index
Yes. The approach I thought of was similar to how to generate the Catalan numbers. You basically just take all the valid strings with n-1 pairs of parentheses and then there are 3 options: You can put () to the left of the string, put () to the right of the string, or put the entire string within a pair of parentheses like ( x ). Any duplicates can be ignored. However, this approach takes a long time because it's recursive. The approach in the video is much faster.
Ez. Your conditions doesn't stop the execution. So on the second stage of recurtion (when you already have one open "(" ) you will call both backtrack functions for another one open "(" and one for the closed ")".
Thanks @NeetCode. Just one quick question. Do you have any suggestions on how to go through the example in virtual interview? I can't imagine trying to explain backtracking solution on code editor ....
Nice. Solution without stack: class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def backtrack(open, close, subResult): if open == close == n: res.append(subResult) return if open < n: backtrack(open + 1, close, subResult + '(') if close < open: backtrack(open, close + 1, subResult + ')') backtrack(0, 0, '') return res
Awesome, and I do agree with a comment that this could've gone into the backtracking section. But reguardless super clear explanation and very concise and clear code!
It took me 2 days to fully understand the question since i was neither Familiar with Trees, DFS nor with Backtracking. so ones who are strictly following the NeetCode Roadmap this question might be a bit tricky to understand. Its Still a Stack question but better suited for Backtracking
Splendid explanation! The explanation was amazing, however when it came to the code implementation, it just didn't make sense anymore. It took me time [and getting obsessed about backtracking] to realise that backtracking doesn't necessarily have to do with trees. I attempted fleshing out a tree with all the possible decisions so I would just return the leaf nodes - since that's what the explanation basically says. Sooner or later, I had to make more research elsewhere.... I later learnt this [please correct me if I'm wrong]: Backtracking has nothing to do with trees. It's just easier to explain the constraints and the decisions using a tree. I wish someone would've pointed that out earlier 😮💨.... Now I'm going to learn backtracking again WITHOUT THINKING IT'S A TREE PROBLEM. However if there's a way to solve this problem USING AN ACTUAL TREE, please do leave a link in the reply 🙏.... Thanks.
Can someone please explain the stack.pop() part. I can't understand why are we removing the value from stack. Wouldn't we need to append it to res at the end?
Can someone explain to me why we do not use a set for the res variable? I know it works, but how come it doesn't fall into making duplicates ? Can anyone clarify that please ?
Great explanation, but how would you explain the time and space complexities? I believe it's bounded by the nth Catalan Number. How in the world am I supposed to prove that during an interview?
I would't say it's better. It really depends on the language, but in the end it's pretty much the same. This explanation with a stack really helped me grasp the solution better as you are actually poping the element after the recursive call.
You should put this problem under the backtracking category and not under the stack one. This is basically a backtracking problem, the stack here is just a helper DS.
I'm so confused! Why are we popping from the stack after appending it. Don't we need a populated stack to append to the result when it reaches the base case?
It’s weird. I get the idea here, or at least I think I do. But something about implementing it in code is really hard for me at this stage. But I’m better than where I was not long ago, so I’ll keep working at it
As I understood it. We need pop() to pass through all combination since '(((' was built and it is basis for nested combinations. Next is removing one '(' by one and find all possible combination.
Can someone tell me the space complexity? I thought to consider the combination formula but we do have rules for neglecting invalid parenthesis, and it's confusing. and the time complexity is O(4^n), right?
Is it still okay to build the tree and return the leaves of the tree? The explanation using Trees is splendid but I honestly don't understand how this code works to makes sure there are multiple different parenthesis combinations...... UPDATE: So I did it with a building a tree... I don't think I am poised to learn about backtracking yet. On leetCode and in other sections, there are various opinions as to what is backtracking and to be honest, this is my first real look at anything related to backtracking.... So I guess I need to do more theory work and practice on backtracking questions so I can understand the patterns and ultimately understand why using just recursion will work... Thank you NeetCode for all that you're doing.
thank u for the intuition, i helped me to clear the basic concept of recursion cpp code : class Solution { public: void PrintP(int open, int close, vector &ans, string s, int n){ // as we are doing by recursion // base condition if(open == n && close == n){ ans.push_back(s); return; } if(open < n){ PrintP(open+1, close, ans, s + "(",n); } if(close < n && close < open){ PrintP(open, close+1, ans, s+")",n); } } vector generateParenthesis(int n) { // this is a pure recursion qs // where we have to print all the well-formed parentheses just like printing // all the subseq // using backtracking vector ans; PrintP(0,0,ans,"",n); return ans; } };
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Thanks for the content, really appreciated as always but I found this video under the stack section. But isn't it a more of backtracking question?
can you add more problems to your new site ?
Thanks! Neetcode. I also recognized the pattern is exactly similar to pre-order depth first search
Think this problem is significantly easier to conceptualize without a stack. You can just use a path variable in the backtrack function and for the conditions where we call backtrack, use path + "(" or path + ")" along with the updated closedN and openN counts. Using a global stack is a bit confusing IMO.
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(open_n, closed_n, path):
if open_n == closed_n == n:
res.append(path)
return
if open_n < n:
backtrack(open_n + 1, closed_n, path + "(")
if closed_n < open_n:
backtrack(open_n, closed_n + 1, path + ")")
backtrack(0, 0, "")
return res
yeah this string solution seems to bit more understandable. Thanks for posting Ryan
Thank you, I think I agree with you. Here are my iterative and recursive solutions:
Iterative:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
parentheses_stack = deque()
parentheses_stack.append(("(", 1, 0))
while parentheses_stack:
s, open_count, close_count = parentheses_stack.pop()
if open_count < close_count or open_count > n or close_count > n:
continue
if open_count == n and close_count == n:
res.append(s)
parentheses_stack.append((s + "(", open_count + 1, close_count))
parentheses_stack.append((s + ")", open_count, close_count + 1))
return res
Recursive:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(s, open_count, close_count):
if open_count < close_count or open_count > n or close_count > n:
return
if open_count == n and close_count == n:
res.append(s)
backtrack(s + "(", open_count + 1, close_count)
backtrack(s + ")", open_count, close_count + 1)
backtrack("(", 1, 0)
return res
I found the stack confusing, this helped thanks 👍
Isn't appending to a string using that method O(N)? So by using that method we would be increasing our time complexity
Actually, it is confusing how making a change in a function call differs from changing it inside the function. If someone got it please explain to me..
I’ve been practicing leetcode for upcoming interviews and I gotta say, your explanations are just so goddamn good. Clear, concise and easy to understand. I don’t know what I would do without these videos.
Same here you mofos
same here
dont use Gods name in vain pls :(
@@gooze3888 oh my god, im so sorry you had to read that
You have this in the stack section of Neetcode but I think it's better in the backtracking section. As someone who is going through neetcode right now, I have reached this problem and it's great to learn but it would be better if it was in the backtracking section since I would be doing repetition on those backtracking questions at that time.
Good point, I think I'll move it
@@NeetCode It is still at stack section and this problem actually blow my mind because of it :D. I wondered how can I use stack in order to solve it but I could not figure out. It would be better to move it imho
@@NeetCode Hey it's still in the stack section, which was a bit of a brain explosion when trying to attempt this question. I look forward to retrying this question once I'm familiar with backtracking, however, as other people have suggested it would be best to move the question to the backtracking section to help out other people in future. Thanks :)
@@NeetCode +1 still in the stack section
@@NeetCode still in stack 😅
This channel is GOLD. Best coding video solution ever.. clean and simple expaination for preparing coding interview !
As soon as you said opening parentheses are less than the number of closing parentheses I got the answer. Finding the happy/sad paths is a really good way to begin tackling these problems.
The level of clarity this guy has!!!! You have all my respect neetcoder
You provide a good explanation to your solution; however, the concept that this problem is meant to focus on is not specifically the stack data structure, it's the backtracking method
I was able to come up with the same idea for solving this. But what blown me away was the implementation. I tried to use DFS using graph to solve this literally taking this idea. But the way you did with the backtracking is so efficient in terms of time and memory. Kudos man 👍
hey, while this problem contains a stack and it is under a stack section on your website I think its more about a backtracking approach. So I reckon its better to move it there. Cheers!
yeah, 1 ~ 2 years later it is still the same and I really struggled finding what the problem does with stacks.
You offer one of the best explanations in YT. Keep up the great work! BTW in your opinion do you think most FAANG engineers could solve questions like these if they have never seen or have done something similar before?
Nope! Everyone needs to learn the technique. After few backtracking problems this one will start looking simple to you.
If they are not aware of backtracking , no they can't.
@@demdimi9316 chance of stumbling on a problem like this at real life job is very thin tbh
I have always admired people who back heir solutions with the recursive tree diagram or the recursive call stack diagram. U have done just that . Thanks and Kudos 🙏🙏😀😀🔥🔥❤️❤️👍👍
for those who are wondering about the time and space complexity, lets break it down, for are essentially having 2^n calls in total, because we have 2 choices at each call, and we go n depths, so its 2^n, each time, we are building an array with n of "()", we can say that upper bound, we have about 2^n leaf call (less than this cos there's duplications and etc.). at each leaf call, we are building the ["(()).."] and append it to our res, so this add about n time for each 2^n leaf node. so runtime will be (2^n) * n, (consider n as 2n cos we have '(' and ')'), spacewise, we use backtrack, we only have 1 arr to build it, but the result will be taking 2^n * n space cos we have to store it and return it. so space and time is about the same. i feel that this question should be marked as recursion or backtracking problem rather than stack.
Just watched 3 minutes from the starting and I was able to code up the solution. Hats off to you man.
I came up with this solution without watching this video -
def generateParenthesis(self, n: int) -> List[str]:
result = []
def recursiveParenthesis(n, op = 0, cl=0, current=""): # 'op' means opening bracket count and 'cl' means closing bracket count
if op>n or cl>n or cl>op: return
if len(current) == 2*n: result.append(current)
recursiveParenthesis(n, op+1, cl, current+"(")
recursiveParenthesis(n, op, cl+1, current+")")
recursiveParenthesis(n)
return result
Glad that the approach is almost similar.
This was definitely a challenging one for me. Thank you for breaking it down the way that you did.
You explain things in the best way and make problems look easy
Wonderful explanation! May I ask what would be the time complexity of the backtracking function?
backtracking is basically a loop, its O(n)
What makes this algorithm go through all possible combinations? Why doesnt the recursion stop after the first combination [ "( ( ( ) ) )"] is added? Like it seems this algorithm would just go through adding three open parenthesis first and then three closed next and would return from the original backtrack call after its added to the result?
It's difficult to visualize because it's backtracking. Conceptually you can think of it as a DFS exploring each allowed "node" or combination. When the DFS call pops from the call stack, it tries to "explore" other "nodes". So after ( ( ( ) ) ) is added, it backtracks all the way to ( ( where it's allowed to add a ) which eventually gives us ( ( ) ( ) ). Then after it backtracks again to ( ( ) ) and we eventually find another answer.
There’s no if else there’s only if so backtrack will work fine
@@halahmilksheikhThank you bro. It is so clear explanation.
I solved this problem but code was too complex and this really helped me out.
I chose to add an extra parameter to the backtrack function to keep track of the currentSolution, it uses less memory and is a little bit faster.
Thank you so muchhh
Didn't understand why we do stack.pop(). Any explanation with a small example will be helpful thanks
What would the time complexity of this backtracking algo be? How would u analyze the time complexity of recursive algos I find it pretty hard sometimes to do that
backtracking with two options has 2^n time complexity, 3 options 3^n etc.. Factorial has factorial time complexity. It all depends
I was struggling a lot with this problem but wonderful explanation of how to break it down to individual components. Thanks a lot
Great explanation, however I still don't understand why you called pop after calling the backtrack function
I am not understanding it well also. Do others have any insights on it?
The reason why is because stack is a global. You have to keep the stack in sync with how the backtracking recursions are behaving. So if you tell the code that we're going to add a (, after when you're done with that backtrack, you have to remove it so the stack is consistent for the next possible recursions.
To put it simply: Each time you push the ( or ) onto the stack, you are effectively saying "Now we're branching off to all possibilities after adding a (" or the same for ")". In the tree he showed, the push onto the stack is just done for each point a node branches out to more nodes, hence we pop it off when we want to go back up the tree and down a different branch
stack keeps track of a single branch of the tree (a single value in the result array), but its being repeatedly passed down each path... need to clear it on the way back up for reuse down the next tree branch. (could also have cloned the stack before pushing onto it... or use an immutable string instead of a stack)
The confusion here might lie because of a false impression that recursive calls of many branches are executed in parallel, indeed they are not, so think about that like this - every path of a tree gets traversed till a final node ( well, leaf ) _consecutively_, though recursive nature of the code does not give such an impression.
That means on every hop of this traversal we just add another element to stack , now when we go back ( traverse reversely ) on every hop we do exactly opposite - remove one element from stack , so we end up with empty stack on the top when we return from the rabbit hole of recursive calls. I still think it’d be better to avoid that complexity and just pass stack or array as a recursive procedure call parameter , this would avoid this type of question 😂
Did it slightly differently. Hope this helps
def generateParenthesis(self, n: int) -> List[str]:
# Create a array to store the result
results = []
# Create a function to recursively form parantheses
def form_parantheses(combination: str, open_parantheses: int, close_parantheses: int) -> None:
# Base case, if the number of close_parantheses > open_parantheses, result is invalid or if the sum of both exceeds total
if close_parantheses > open_parantheses or (open_parantheses + close_parantheses) > (n * 2):
return
# Second Base case, if the number of open_parantheses is equal to each other and to n * 2, we have a valid solution
if open_parantheses + close_parantheses == n * 2 and open_parantheses == close_parantheses:
results.append(combination)
return
# We have two decisions here, either we can add an open parantheses or a closed one
form_parantheses(combination=combination + "(", open_parantheses=open_parantheses + 1, close_parantheses=close_parantheses)
form_parantheses(combination=combination + ")", open_parantheses=open_parantheses, close_parantheses=close_parantheses + 1)
form_parantheses(combination="", open_parantheses=0, close_parantheses=0)
return results
I don't understand how the code produces all 5 different outputs for when the case is 3 (as example). I only understand how it does the following one: ((())), but how does it randomly generate the other solutions such as (())()???
Hey could you make the explanation of time and space complexity of the solution a separate TH-cam video chapter?. Great videos btw...I think whenever I'm just reviewing problems via your videos, just having that chapter will make it really easy for people for myself. Thanks.
If Neetcode hasn't gone into space and time complexities it usually means it is too hard to evaluate that. Hehehe.
I felt below solution to be more intuitive to understand:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def back_track(string, leftCount, rightCount):
if len(string) == n * 2 :
res.append(string)
return
if leftCount < n:
back_track(string + '(', leftCount + 1, rightCount)
if rightCount < leftCount:
back_track(string + ')', leftCount, rightCount + 1)
back_track('', 0, 0)
return res
Personnally, I also didn't understand why this problem was in stack section at first, but considering the low cap on the input value (
Hey man love your stuff, what program/software do you use for the drawings/illustrations?
extremely clear explanation thank you
Thanks 😊
Love the explanation, thanks for the video. Can someone please tell the time and space complexity of this ?
The simplicity simply blew my mind. thank you @NeetCode
What is the Time Complexity?
Hey, did you explain about the time complexity in this video? I've watched and I didnt see... I asked chatGPT about it and explained about O((4^n)/(n^(3/2)) time
A quick note, if C# or Java are used and you use the built in Stack insert the parenthesis in a reverse order.
Call me pedantic but parenthese is not a word. The singular form is parenthesis. PARENTHESIS! I'd also accept "bracket". Aside from that, amazing video! 👏
wow, bro loved the solution and this condition is the main crux of the prob closed_count < open_count to add closed bracket
Your explanation made me fall in love with this problem!!! Thank you
Hello, I am confused why we pop the character symbol we just added. Could you explain this?
What i observed was if we add two balanced paranthesis the resulting string will also be balanced. So I started with the base '( ) ' for n=1 and just added the same recursively at every index
Yes. The approach I thought of was similar to how to generate the Catalan numbers. You basically just take all the valid strings with n-1 pairs of parentheses and then there are 3 options: You can put () to the left of the string, put () to the right of the string, or put the entire string within a pair of parentheses like ( x ). Any duplicates can be ignored. However, this approach takes a long time because it's recursive. The approach in the video is much faster.
perfect explanation of a complicated topic. Thank you
woah I don't get this, how does this generate every combination when the starting point and conditions are always the same?
Ez. Your conditions doesn't stop the execution. So on the second stage of recurtion (when you already have one open "(" ) you will call both backtrack functions for another one open "(" and one for the closed ")".
Thanks @NeetCode. Just one quick question. Do you have any suggestions on how to go through the example in virtual interview? I can't imagine trying to explain backtracking solution on code editor ....
Nice. Solution without stack:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def backtrack(open, close, subResult):
if open == close == n:
res.append(subResult)
return
if open < n:
backtrack(open + 1, close, subResult + '(')
if close < open:
backtrack(open, close + 1, subResult + ')')
backtrack(0, 0, '')
return res
Awesome, and I do agree with a comment that this could've gone into the backtracking section. But reguardless super clear explanation and very concise and clear code!
It took me 2 days to fully understand the question since i was neither Familiar with Trees, DFS nor with Backtracking. so ones who are strictly following the NeetCode Roadmap this question might be a bit tricky to understand. Its Still a Stack question but better suited for Backtracking
Mind blowing explaination i wish i could understand coding as good as you
That recursion tree is absolutely nuts to have to write out, and nigh impossible to actually visualize without it (8:15)
Great Video! thanks for explaining this in a such easy way but
can u explain why we need the latter pop ?
really appreciate your explanation - very clear
These solutions are so much better than Leetcode's 'official' ones
Great explanation but I didn't understand what exactly pop() is doing?
Nice one.. what's the time complexity of this algorithm ?
Splendid explanation! The explanation was amazing, however when it came to the code implementation, it just didn't make sense anymore. It took me time [and getting obsessed about backtracking] to realise that backtracking doesn't necessarily have to do with trees. I attempted fleshing out a tree with all the possible decisions so I would just return the leaf nodes - since that's what the explanation basically says. Sooner or later, I had to make more research elsewhere....
I later learnt this [please correct me if I'm wrong]: Backtracking has nothing to do with trees. It's just easier to explain the constraints and the decisions using a tree. I wish someone would've pointed that out earlier 😮💨.... Now I'm going to learn backtracking again WITHOUT THINKING IT'S A TREE PROBLEM. However if there's a way to solve this problem USING AN ACTUAL TREE, please do leave a link in the reply 🙏.... Thanks.
Thank You So Much Brother...............This helped a lot........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Can someone please explain the stack.pop() part. I can't understand why are we removing the value from stack. Wouldn't we need to append it to res at the end?
Same query
Can someone explain to me why we do not use a set for the res variable? I know it works, but how come it doesn't fall into making duplicates ? Can anyone clarify that please ?
Thanks for explanation. BTW, time & space complexity analysis is important
What is the time and space complexity for this program?
great explanation
i wish i have explanation skills like you
short and best explanation for this question❤❤❤❤
Is this O(2^n) time complexity and O(n) space?
Extremely well explained
Great explanation, but how would you explain the time and space complexities? I believe it's bounded by the nth Catalan Number. How in the world am I supposed to prove that during an interview?
There is a better solution not involving stack, you can just append "(" or ")" as you call backtrack function, depending on condition ofc.
I would't say it's better. It really depends on the language, but in the end it's pretty much the same.
This explanation with a stack really helped me grasp the solution better as you are actually poping the element after the recursive call.
genius analysis and solution... wow!!! I wish I could just bring you to the interview with me! 🤣🤣
Damn, how can you make anything easy to understand!I really appreciate your work and it is very helpful for me.
why pop()? seems remove the pop it also works
your solutions are actually beautiful
Best leetcode channel ever! Thank you for all that you do!
TBH, this doesnt require stack at all. Refer to my solution in Java :
Java Code :
public List generateParenthesis(int n) {
List ans = new ArrayList();
generateAll(ans,"",0,0,n);
return ans;
}
public void generateAll(List ans,String str,int oc,int cc,int n){
if(oc==cc && oc==n && cc==n){
ans.add(str);
return;
}
if(oc < n){
generateAll(ans,str + "(",oc + 1,cc,n);
}
if(cc < oc){
generateAll(ans,str + ")",oc,cc+1,n);
}
}
You should put this problem under the backtracking category and not under the stack one. This is basically a backtracking problem, the stack here is just a helper DS.
You are amazing!!! You explanation is soooooooo clear! Thank you!
Such a brilliant solution! I m struggling with backtracking and recursion in general because I can't seem to visualize, any tips?
Keep track of the function call that you are in and make sure to not confuse it with the function call being made.
I'm so confused! Why are we popping from the stack after appending it. Don't we need a populated stack to append to the result when it reaches the base case?
I don't get it either. Seems overly complicated to me than the simpler backtracking methods.
This is not a stack problem, but a backtracking one.
It’s weird. I get the idea here, or at least I think I do. But something about implementing it in code is really hard for me at this stage. But I’m better than where I was not long ago, so I’ll keep working at it
What is the Time and Space complexity?
very good explanation!
Hey mate. Great Vidoes. What is the complexity of the above solution ?
can someone please explain why pop is used?
In the recursive solution you build the state before recurring then once you return you restore the state it was prior to the recur.
As I understood it. We need pop() to pass through all combination since '(((' was built and it is basis for nested combinations. Next is removing one '(' by one and find all possible combination.
legend when it comes to explanation.
Can someone tell me the space complexity? I thought to consider the combination formula but we do have rules for neglecting invalid parenthesis, and it's confusing. and the time complexity is O(4^n), right?
i did not understand the flow , after the return statement in backtrack function
can anyone explain it to me plese
Let's take n = 2.
We make the function call Backtrack (0,0) where n =2
There are there conditions: openN=closeN=n, openN
Why u are pop stack character I can't understand 😢
Amazing explanation!!!
The singular of parentheses is parenthesis, not "parenthesee".
anyone know what tools is he using for the starting explaination part, for drawing on screen (which app etc.)?
This question really threw me off in the stack section, since I didnt' really think of recursion at all.
Would the solution work if u did if/else if/else instead of 3 ifs?
Is it still okay to build the tree and return the leaves of the tree? The explanation using Trees is splendid but I honestly don't understand how this code works to makes sure there are multiple different parenthesis combinations......
UPDATE:
So I did it with a building a tree... I don't think I am poised to learn about backtracking yet. On leetCode and in other sections, there are various opinions as to what is backtracking and to be honest, this is my first real look at anything related to backtracking.... So I guess I need to do more theory work and practice on backtracking questions so I can understand the patterns and ultimately understand why using just recursion will work...
Thank you NeetCode for all that you're doing.
Try watching back to back SWE for backtracking
2:02 bro made smiley with out knowing
I like how you spelled "Parentheses" in the coding explanation lol
I really think this should be categorized as a backtracking problem instead of a stack problem
Could you give the time complexity for the solution of "Generate Parentheses" problem you demonstrated? @NeetCode
thank u for the intuition, i helped me to clear the basic concept of recursion
cpp code :
class Solution {
public:
void PrintP(int open, int close, vector &ans, string s, int n){
// as we are doing by recursion
// base condition
if(open == n && close == n){
ans.push_back(s);
return;
}
if(open < n){
PrintP(open+1, close, ans, s + "(",n);
}
if(close < n && close < open){
PrintP(open, close+1, ans, s+")",n);
}
}
vector generateParenthesis(int n) {
// this is a pure recursion qs
// where we have to print all the well-formed parentheses just like printing
// all the subseq
// using backtracking
vector ans;
PrintP(0,0,ans,"",n);
return ans;
}
};
super intuitive video thank you for posting
Love your explanation
phenomenal video 🤯
@neetcode can you please explain the time and space complexity for this problem?