Generate Parentheses

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.

Problem Statement

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

Example 01:

Input:  n = 3

Output : 
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Example 02:

Input:  n = 1

Output : ["()"]

Constraints: 1 <= n <= 8

Thought Process

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.

Algorithm

Let us walk through a backtracking algorithm.

Instead of adding '(' or ')' 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.

Solution

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
        System.out.println(generateParenthesis(1));
    }

    public static List<String> generateParenthesis(int n) {
        List<String> output = new ArrayList<String>();
        backtrack(output, "", n, 0, 0);
        return output;
    }

    public static void backtrack(List<String> output, String currString, int max, int open, int close) {
        //base case
        if (currString.length() == max * 2) {
            output.add(currString);
            return;
        }

        if (open < max) {
            backtrack(output, currString + "(", max, open + 1, close);
        }
        if (close < open) {
            backtrack(output, currString + ")", max, open, close + 1);
        }
    }
}