Backtracking - Generate Parentheses

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

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

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

Constraints:

0 <= n <= 8

Solution 1 - Using Backtracking

In this approach, we are going to apply Backtracking technique, i.e. we are going to construct a decision tree with the valid rules and solve the problem recursively.

Valid Rules:

A valid parenthesis always have to start with an opening bracket '('.
When there are equal number of opening and closing brackets, but current brackets count is less than n, then next bracket should be an opening bracket. For example, say n = 3 and current parentheses are ()() or (()), next bracket should be an opening bracket ( otherwise, it will make it invalid parentheses.

Let's look at an example with n=3, when we apply above rules, decision tree will look like this, at each level we will check with both possibilities of adding a left bracket '(' or a right bracket ')'. As you can see below, there are 5 valid parentheses can be drawn from n=3. decision tree with n=3

Implementation steps:

First, we will create a helper function that we are going to call recursively, that takes following arguments.
- n, input parameter.
- openN, number of open brackets in current parentheses.
- closeN, number of close brackets in current parentheses.
- stack, stack of characters in current parentheses, reason we chose Stack is because at each step we will try with possibilities of an opening and closing brackets, after trying one option (considering an opening bracket) we will remove the top element and try with other option (considering closing bracket).
- result, result List that we will add the output into.
Next, check if we hit the base case. That is if openN count is equal to closeN and they are also equal to n, this means we have used all choices of opening and closing brackets, now we can construct a string out of the characters from stack and add to result list.
Then, check if openN < n, this means that opening bracket choice is possible, so add the current character '(' into stack and call this helper function recursively, once this loop ended, remove the top element from stack.
Then, check if closeN < openN, this means that we can consider a closing bracket, so add the current character ')' into stack and call this helper function recursively, once this loop ended, remove the top element from stack.
Call above helper function with inputs n, 0, 0, empty stack and empty result list.

import java.util.ArrayList; import java.util.List; import java.util.Stack; import java.util.stream.Collectors; public class GenerateParentheses { static List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); helper(n, 0, 0, new Stack<>(), res); return res; } static void helper(int n, int openN, int closeN, Stack<Character> stack, List<String> result) { if(openN == closeN && openN == n) { result.add(stack.stream().map(String::valueOf).collect(Collectors.joining())); return; } if(openN < n) { stack.push('('); helper(n, openN+1, closeN, stack, result); stack.pop(); } if(closeN<openN) { stack.push(')'); helper(n, openN, closeN+1, stack, result); stack.pop(); } } public static void main(String[] args) { System.out.println(generateParenthesis(3)); } }

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) since we are calling helper function recursively, with all possibilities.
Space complexity: O(n), since we are calling the helper function recursively, this is the memory used by memory stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: