Generating all combinations of well-formed parentheses.

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

My solution to this week's interview question from cassidoo's weekly newsletter.


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


$ formParens(1)
$ ["()"]

$ formParens(3)
$ ["((()))","(()())","(())()","()(())","()()()"]


The solution involves a couple of steps:

1- Forming a string that has the correct number of parentheses. This should be straightforward.

2- Take the string from step #1, and generate all the unique permutations for that string.

3- Check each output from step 2 to see if it is valid or not using a stack.

Now, I forgot how to generate permutations of a strings so I looked it up and I found an approach that I like in this article so I am going to use it in my solution.


import java.util.*;

class Main {

  private static ArrayList<String> permutationList = new ArrayList<>();
  private static ArrayList<String> resultList = new ArrayList<>();
  public static void main(String[] args) {

  public static void solution(int n) {
    String s = "";
    for(int i=0; i < n; i++) {
      s += "()";
    findPermutations(s.toCharArray(), 0);
    for(int i = 0; i < permutationList.size(); i++) {
      Stack<String> stack = new Stack<String>();
      String permutation = permutationList.get(i);
      boolean isValid = true;
      for(int j= 0; j<permutation.length(); j++) {
        String c = permutation.charAt(j) + "";
        if (c.equals("(")) {
        } else {
          if(!stack.isEmpty()) {
          } else {
            isValid = false;
      if (!isValid) {


  public static void swap(char[] s, int i, int j) {
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;

  public static void findPermutations(char[] s, int currentIndex) {
    if(currentIndex == s.length -1) {

    for(int i = currentIndex; i<s.length; i++) {
      swap(s, currentIndex, i);
      findPermutations(s, currentIndex+1);
      swap(s, i, currentIndex);

Time complexity: O(n!) where n is the is the length of the string with all the opening and closing parenthesis generated in step 1.

Interactive Replit:

You can run the code and see the results in this replit:

Subscribe to Faisal.Software

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.