LeetCode 22. How Backtracking works - Generate Parentheses [Algorithm + Code Explained ]

A classic example of Backtracking algorithm. I have added a seperate section to help understand how backtracking works.

One of the most frequently asked coding interview questions on Arrays in companies like Google, Facebook, Amazon, LinkedIn, Microsoft, Uber, Apple, Adobe etc.

LeetCode : Generate Parentheses

Question : Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

[SarthakKumar]

Seriously, this is an underrated channel for real. I mean the explanation is just flawless and concept visualization is so clear and to the point! Thank you so much ma'am. Please don't stop here, keep making these videos it can bring a lot of careers on track.

[soumikpaul]

I had gone through many videos for this problem but this is the one I got to understand in one go.
and please keep uploading more videos

[SameerSrinivas]

Thanks for your effort. Really liked the fact that you wrote recursive tree calls along with an explanation for complexities.

[jordanyang]

Love your explanation at the end!! Some people just show the code w/o explaining how the code works.

[sainagachaitanyaporanki]

I love to see more bt problems on this channel.

[harinijeyaraman]

This video deserves a lot more likes and views !! Found this very helpful !! Thanks a ton <3

[samahome]

Great explanation. Kudos on showing the step-by-step chart explanation.

[sauravkumarsonu]

Really a gem video for understanding the backtracking, excellent explanation ❤️👏

[vardaanbajaj]

this video is such a good explanation for backtracking in general as well. i have always struggled with backtracking but this video helped a lot. your style of thinking out loud helps develop a thought process. good work.

[danqingreader]

Nice video. Thanks a lot for your explanation about the process of backtrack. I learn much from it!

[radhikabhatia]

Thanku so much this video was very helpful

[astronautatul]

thanks for understanding the concept of backtracking 🙂

[Roy-ztsl]

Great explanation. Will you share the Approach chart you were showing? 0:45

[SuvradipDasPhotographyOfficial]

This is the video that helped me understand backtracking in the easiest possible way. Thanks a lot mam for this problem series.

[durjaarai]

Can you share notes on some of the strategies to follow for every problem like you showed in the first slide

[neerajanand]

Nice work, keep doing! The way u explained was really nice. Thanks

[sivaramakrishnaganta]

Great Explanation Jayati, but it is only a recursion approach. You are not using backtracking here like you are not nonperforming the already performed actions or abandon the sub problems. Please verify it once.

Adding to that, a backtracking solution would be like this, it's just a small modification to your code.

class Solution:

def fun(self, res, s, open, close, n):
if(len(s) == 2*n):
res.append(''.join(s));
return
if(open < n):
s.append('(');
self.fun(res, s, open + 1, close, n);
s.pop()
if(close < open):
s.append(')')
self.fun(res, s, open, close + 1, n);
s.pop()



def generateParenthesis(self, n: int) -> List[str]:
res = []
s = []
self.fun(res, s, 0, 0, n);
return res;

[chinthamokshith]

Could you explain what would be the next step in flow chart in case of n=3

[sunshodan]

Could you do some problems on backtracking on matrices.

[hemanthn]

miss expecting more problems like this from you...