Backtracking or Stack ????
Yeah its been a while. I have end semester exams, so focusing on that.
Today, however I got bored of studying for the exam and thought about doing some leetcode.
I follow the roadmap set out by neetcode.io. I am currently in the stack section. The problem you might ask ?
Generate Parentheses ()()()..
The problem goes like this, you are given a number which represents the pair of parentheses. Using this generate all the possible combinations of valid parentheses (Valid as in, open parentheses should come before the closed parentheses). For example,
Input = 1 , Output= ()
Input = 3, Output= ()(()) (())() ()()() (()()) ((()))
This was an interesting problem, cause I didn’t get how a stack would be used here and, under the topics section in leetcode, it is written backtracking, dynamic programming and string. There was no relation to stack. I completely ditched the idea of solving it with a stack.
So, with the problem understood and the blank is zero, we move on to the solution.
🧠 My Genius Solution
First order of business, I need to figure out how this question is related to backtracking. My experience in backtracking is not great. My brain goes in smoke when I start thinking about recursive functions.
Get Njan.Codes’s stories in your inbox
Join Medium for free to get updates from this writer.
However, I had 2 or 3 questions which related to backtracking that I had solved. All of them consisted a tree. What is a tree you ask ??
So, with this idea in mind, I was trying to fit the problem to a tree and it clicked. I have a starting open parentheses, then I add an open parentheses and in another state a closing parentheses. Then the newly formed parentheseses (Is that the plural form of parentheses ??? ) will be going through that again, adding more and more open or closed parentheses. After a certain amount of iterations (I will discuss this arbitrary amount), it will output all the possible combinations. You can visualize it by the below chart from leetcode discussions.
Some of the nodes have been deleted, that is because they are not valid. However, I still compute those nodes. After creating the whole tree, I check for nodes which are at the bottom (and has no nodes connected underneath to it) and check if they are valid. If they are valid, then output it, else discard it.
Here, you might be asking how many iterations have to be made to reach that tree. This number isn’t arbitrary but a calculated number. The number of iterations to take is 2 times the input given. I reached that conclusion by drawing the tree myself for other inputs. The number of iterations was always double the input.
Putting all that information as code in leetcode, I solved the problem. Whooorayyyyyy 🎉🎉🎉🎉🎉🎉
This was a a fun problem. However, I still wonder why this question was under the stack section, that is probably neetcode’s mistake.
Caution: This solution is not efficient but gets the job done. For more efficient solution watch this video.
I have stopped my development on the extension due to exams. If I do have any updates I will blog about it. Don’t worry I haven’t abandoned it.
Thank you and that’s all is there to it for today.
