## DEV Community is a community of 850,636 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

kevin074

Posted on

# Leetcode diary: 22. Generate Parentheses [DFS]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This is definitely easy of medium question, could be marked easy honestly.

I am having major depression and confidence fell into abyss from trying to do a hard problem. Wanted to do a trilogy of it, since there are 3 of the similar premise problem. Alas I was only able to do the medium questions and come to nothing close to the solution for the hard level problem. Woe is me, fuck it I'll just do something that I know would be easy just from reading the title of the problem.

This is a simple "generate all" type of question. Whenever you see a problem like this the go-to strategy is DFS. The question asks to generate all valid parenthesis. If you aren't familiar with parenthesis questions, just know that the only restriction is that you always have to have at least 1 more left parenthesis than right before you add a right parenthesis.

Therefore the thought process for this question is:
1.) use DFS somehow
2.) keep track of left and right parenthesis number via ints
3.) as you use DFS to generate the "tree", just check for left > right before calling recursion adding the right parenthesis
4.) another condition to stop adding left parenthesis once left === 0;
5.) the end condition is when both left and right === 0, at this point you add the parenthesis permutation to the answer array.

code:

``````var generateParenthesis = function(n) {
const left = n;
const right = n;

function recur (left, right, current) {
if(left === 0 && right ===0) {
return;
}

if(left > 0) {
recur(left-1, right, current.concat(["("]))
}
if(right > left) {
recur(left, right-1, current.concat([")"]))
}
}

recur(n,n,[])