Solve generate parentheses problem

In this post we will try to print out all combinations of valid parentheses for a given number n

Problem Statement :

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:

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

Step by step solution to the problem :

To generate all combinations of parentheses we can use backtracking as mostly all combinations related problem can be solved using backtracking.

We will keep track of two variable as open and close initialized to 0, which signifies number of open and closed parentheses in the current output string.Our backtracking function will look as below:

Whenever we get open ==n and close ==n we add the current string to result array and backtrack to last steps where we added ‘(‘ , to add ‘)’ to get different combination of result. Ultimately our result list will have all the combinations.

The complete code for this problem can be found in https://github.com/GyanTech877/algorithms/blob/master/backtracking/GenerateParentheses.java

Happy Learning 😎