Problem

Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.

OR

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Follow up

Make sure the returned list of strings are sorted.

Examples

Example 1:

1
2

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

1
2

Input: n = 1
Output: ["()"]

Solution

This is a classic combinatorial problem, appearing in various forms. These strings, known as Dyck strings (see more here), consist of ( n ) X’s and ( n ) Y’s, ensuring no initial segment has more Y’s than X’s. Examples include:

1

XXXYYY, XYXXYY, XYXYXY, XXYYXY, and XXYXYY.

Similar problems include:

  • Generating all balanced parenthetical expressions for ( N ) pairs (i.e., this problem)
  • Creating all possible ways to apply a binary operator to ( N + 1 ) factors
  • Forming all full binary trees with ( N + 1 ) leaves

Solution

Method 1 - Backtracking

We have to keep track of open and close parentheses. Main idea is that we should add ')' only after valid '('. So, we can take 2 integer variables - open and close, to keep track of open ( and close ) parentheeis. Then our recursion follows the rule:

  • if open is less than n, we can add ( to the current string
  • if close is less than open, we can add ) to the current string

Here is how the recursion tree will look:

graph TD
	A[" "]
	A --> |"("| O["("]
	O --> |"("| O2["(("]
	O --> |")"| OC["()"]
	
	O2 --> |"("| O3["((("]
	O3 --> |")"| O3C["((()"]
	O3C --> |")"| O3C2["((())"]
	O3C2 --> |")"| O3C3["((()))"]:::answer

	OC --> |"("| OCO["()("]
	OCO --> |"("| OCO2["()(("]
	OCO2 --> |")"| OCO2C["()(()"]
	OCO2C --> |")"| OCO2C2["()(())"]:::answer


	O2 --> |")"| O2C["(()"]
	O2C --> |"("| O2CO["(()("]
	O2CO --> |")"| O2COC["(()()"]
	O2COC --> |")"| O2COC2["(()())"]:::answer

	OCO --> |")"| OCOC["()()"]
	OCOC --> |"("| OCOCO["()()("]
	OCOCO --> |"("| OCOCOC["()()()"]:::answer

	O2C --> |")"| O2C2["(())"]
	O2C2 --> |"("| O2C2O["(())("]
	O2C2O --> |"("| O2C2O2["(())()"]:::answer

	
	classDef answer fill:green,stroke:#333,stroke-width:2px;

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        if (n == 0) {
            return ans;
        }
        helper(n, "", 0, 0, ans);
        return ans;
    }


    private void helper(int n, String current, int open, int close, List<String> ans) {
        if (current.length() == n * 2) {
            ans.add(current);
        }

        if (open < n) {
            helper(n, current + "(", open + 1, close, ans);
        }
        if (close < open) {
            helper(n, current + ")", open, close + 1, ans);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
	public List<String> generateParenthesis(int n) {
	     List<String> ans = new ArrayList<>();
	     helper(n, new StringBuilder(), 0, 0, ans);
	     return ans;
	}
	
	private void helper(int n, StringBuilder sb, int open, int close, List<String> ans) {
	    if(open == n && close == n) {
	        ans.add(sb.toString());
	        return;
	    }
	    
	    if(open < n) {
	        sb.append("(");
	        helper(n, sb, open + 1, close, ans);
	        sb.setLength(sb.length()-1);
	    } 
	    if(close < open) {
	        sb.append(")");
	        helper(n, sb, open, close + 1, ans);
	        sb.setLength(sb.length()-1);
	    }
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def generateParenthesis(n):
    def backtrack(S="", left=0, right=0):
        if len(S) == 2 * n:
            result.append(S)
            return
        if left < n:
            backtrack(S + "(", left + 1, right)
        if right < left:
            backtrack(S + ")", left, right + 1)

    result = []
    backtrack()
    return result

Complexity

  • ⏰ Time complexity: O(2^n) because at each step, we either open or close a parenthesis. That is the upper bound. But actually, if we do the counting, when we count number of valid parentheses, it is equal to catalan number, i.e. C(n) = 2n! / (n + 1)!(n!). More on it: Catalan Numbers.
  • 🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Top Down DP

Here’s how you can implement this approach:

  1. Recursive Function with Memoization:

    • Use a dictionary (or a map) to store previously computed results for specific numbers of pairs.
    • Recursively generate combinations by placing pairs in every valid position.
    • Memoize results to avoid recomputation.

  2. Base Case:

    • When (n = 0), the only result is an empty string.

Try to visualize the below code with memo map:

1
2
3
4

memo[0] = [""]
memo[1] = ["()"]
memo[2] = ["()()", "(())"]
memo[3] = ["((()))", "(()())", "(())()", "()(())", "()()()"]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
	public List<String> generateParenthesis(int n) {
	     Map<Integer, List<String>> memo = new HashMap<>();
	     memo.put(0, List.of(""));
	     return helper(n, memo);
	}
	
	private void helper(int n, Map<Integer, List<String>> memo) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        List <String> ans = new ArrayList<>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int i = 0; i < n; i++) {
                for (String left: dp(i, memo)) {
                    for (String right: dp(n - 1 - i, memo)) {
                        result.add("(" + left + ")" + right);
                    }
                }
            }
        }

        memo.put(n, result);
        return result;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def generateParenthesis(n):
    memo = {}

    def dp(i):
        if i in memo:
            return memo[i]

        if i == 0:
            return [""]

        result = []
        for j in range(i):
            for left in dp(j):
                for right in dp(i - 1 - j):
                    result.append(f"({left}){right}")
        memo[i] = result
        return result

    return dp(n)

Method 3 - Bottom up DP

We use a dynamic programming table where each entry dp[i] represents all possible combinations of i pairs of well-formed parentheses. Let dp[i] represents all well-formed combinations of i pairs of parentheses.

Recurrence relation

To get dp[i], you can think of it as placing a pair of parentheses () in every possible position around combinations of smaller pairs: $$ dp[i] = \sum_{k=0}^{i-1} \text{( “(” + dp[k] + “)” + dp[i-1-k] )} $$

This means placing dp[k] inside (), and then concatenating it with all valid combinations of dp[i-1-k].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public List < String > generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList < String > () {{
                add("");
            }};
        }

        List < List < String>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        dp.get(0).add("");

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                for (String left: dp.get(j)) {
                    for (String right: dp.get(i - 1 - j)) {
                        dp.get(i).add("(" + left + ")" + right);
                    }
                }
            }
        }

        return dp.get(n);
    }

}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def generateParenthesis(n):
    if n == 0:
        return [""]

    dp = [[] for _ in range(n + 1)]
    dp[0] = [""]

    for i in range(1, n + 1):
        for j in range(i):
            for left in dp[j]:
                for right in dp[i - 1 - j]:
                    dp[i].append(f"({left}){right}")

    return dp[n]

Method 4 - Level Order Traversal

Let’s start with the base cases:

  • n = 0: The result set is empty (no solution).
  • n = 1: The result set is {()}.

For n = 2, we can build the result set by inserting a new pair “()” into all gaps in each result from n = 1. For example, the only solution for n = 1 is () with 3 gaps, as shown:

1
2
3

      (  )
     ^  ^  ^
    g1  g2  g3

To get the result for n = 2, we append “()” in each gap of the solutions from n = 1, leading to:

1
2
3

     ()()         (())       ()()
     ^             ^           ^
    g1             g2          g3

The unique result set for n = 2 is {()(), (())}. Generally, there are m+1 gaps in a string of length m. We can construct a string with n parentheses by inserting “()” into each of the m+1 gaps in the solutions of length m for n-1.

To implement this, formulate the problem as a tree traversal problem. Starting from n = 1 as the root “()”, we traverse m+1 = 3 children corresponding to the string constructed by inserting “()” into the m+1 gaps. The nodes at level n of this tree will contain all possible strings with n pairs of parentheses. For instance:

1
2
3
4
5

                        ( )           <- n = 1
                   /     |    \ 
            ( ) ( )   (())   ()()     <- n = 2
           / |  \ \ \      
     ()()() (())()     .........      <- n = 3

We can perform a level order traversal using a queue and stop at level = n, at which point the queue will contain the result set for n. For more details on the level order traversal algorithm using a queue, refer to my previous note on finding the rightmost cousin of a binary tree. The following is a simple implementation of this idea.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public static ArrayList<String> genParanthesis(int n) {
	ArrayList<String> ans = new ArrayList<String> ();
	if (n<= 0) {
		return ans;
	}
	if (n == 1) {
		ans.add("()");
		return ans;
	}

	Queue<StringBuilder> queue = new ArrayDeque<StringBuilder> ();
	Set<String> visited = new HashSet<String> ();
	queue.add(new StringBuilder("()"));
	int count = 1;
	int level = 1;

	//do a level order (BFS) trversal upto level=n
	while (!queue.isEmpty()) {
		StringBuilder node = queue.poll();
		String cur = node.toString();
		count--;
		visited.add(cur);

		//at the end of level order traversal upto level n the queue will contain all the leaves at level n
		//which are basically all possible strings constructed with n pair of parenthesis
		if (level == n) {
			ans.add(cur);
			continue;
		}

		//if not reached level n yet, then do BFS level order
		//there are total 1+len(cur) gaps
		for (int gap = 0; gap<cur.length() + 1; gap++) {
			//we create a child by putting () to each of the gap positions
			StringBuilder child = new StringBuilder(cur).insert(gap, "()");
			if (!visited.contains(child.toString())) {
				queue.add(child);
				visited.add(child.toString());
			}
		}

		//end of a level
		if (count == 0) {
			level++;
			count = queue.size();
		}
	}

	return ans;
}