Generate Parentheses - Leetcode 22 - Recursive Backtracking (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@saaddude1]

Love you explanations, by far the best on the internet! It makes these problems so much easier to understand and code. Please upload DSA 150 as these will be more helpful for those preparing for interviews.

[@GregHogg]

Thank you! And I'll try haha

[@Redaxi]

When im stuck at backtracking i listen to your explanations without looking at your code and in the middle of the explanation something just clicks and then i go and am able to solve it immediately. Hopefully with time i can start solving without the need of your explanations ^^ Thanks for everything tho

[@ArdianUmam]

Thanks, Greg! Btw, wanna share the modified version using a string, instead of a list. We can just append each character "(" or ")" to the string in the function parameter. class Solution: def generateParenthesis(self, n: int) -> List[str]: result = [] def rec(n_open, n_close, parenthesis): if len(parenthesis) == (2*n): result.append(parenthesis) return if n_open < n: rec(n_open+1, n_close, parenthesis+"(") if n_close < n_open: rec(n_open, n_close+1, parenthesis+")") rec(n_open=0, n_close=0, parenthesis="") return result

[@chandlerkenworthy3185]

The problem with this approach is that adding characters to a string is in general an O(n) operation but appending to a list is generally O(1). It is therefore much faster to use a list and join at the end.

[@SaPpHiRe051918]

Subbed. Great explanation. Also base condition could be if (open==n && closed==n) then append.

[@SelftaughtSoftwareEngineer]

Thanks for the video! What software did you use for the whiteboarding? Do you use a special pen or just a mouse to write?

[@tushitapatel5782]

With n=8, there are 1430 combinations. That's 1430 combinations of size (2*n). The space complexity is not O(n).

[@tushitapatel5782]

What is it??

[@derrickagyemangduah2353]

@@tushitapatel5782 O(2^n)

[@anton_melnikov]

i dont understand two things: 1. why do we need to pop after we add a parenthesis. if we pop, wouldn't sol be an empty list (and then how an empty list would be used in appending to ans?)? 2. why would this algorithm not stop after getting the first combination "((()))"?

[@ahmadbasyouni9173]

My advice to you is to use pen and paper and go through the tree it will click in, but the way i like to understand it is to look all the way at the first case you wanna ignore the deeper levels of the tree so if u look at 4:13 initially we are able to add open, so thats the first if statement, and we will add it and call the backtracking function for when u have an open. But when all of that finishes to the left of the root, we need to backtrack up and explore the right branch as if we didnt add a opeing (add closing). Therefore we have the pop at the end of first if. The second pop in the second if statement is if you are in the left tree still at 4:13 and at that call went down the second if statement you see how u add a close parantheses but what happens after this call is u need to back track back up so ur able to explore the right side of the root like we said therefore u need to "clean up".

[@rahulreddy4944]

The TC is wrong