Generate Parentheses

Problem description:

Given a non negative number n, generate all possible combinations of strings that can be formed by n-pairs of well-formed parentheses, for example:

for n = 2
a solution is: “(())”, “()()”

and for n = 3
a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”


We could use a simple Depth First Search (DFS) approach to recursively build the set of solutions, see the solution code below and then read the explanation:

    void generateParentheses(int n) {
        dfs("", n, n);
    void dfs(String s, int left, int right) // build the set of solutions using DFS approach
        if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
        if(left > 0) // while we have left parentheses to add, just add them
            dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
        if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
            dfs(s + ")", left, right - 1);

Let’s work on the simplest example to explain how it works:

for n = 2 we know that we have 2 left parentheses and 2 right parentheses so for each recursive call we are going to take 2 decisions:
1.- Can we put a left parentheses?
2.- Can we put a right parentheses?

How do we know if we are able to put a left or right parentheses at each recursive call?
We can put a left parentheses as long as we have at least one left parentheses available but for the right ones we can add them only when we have more right parentheses available because we know that we have already added the corresponding left parentheses before adding the right one.

Do you have any question/comment/suggestion? Please leave your comment below.