In Generate Parentheses problem, we input a number and our algorithm needs to generate all the valid pairs of parentheses. There are millions of ways to achieve this. Let us use one of the well-known backtracking algorithms to solve this.
n pairs of parentheses, write a function to generate all combinations of well-formed parenthesis.
Input: n = 3 Output : [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
Input: n = 1 Output : ["()"]
1 <= n <= 8
This problem can be solved in tons of different ways, by making use of dynamic programming or backtracking algorithm or just using a Stack data structure, etc. With this let’s try to break the problem into smaller chunks so solving these smaller chunks altogether yields the solution for the entire problem.
Let us walk through a backtracking algorithm.
Instead of adding
')' every time. let’s only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far. We can start an opening bracket if we still have one (of
n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.