Generating all combinations of well-formed parentheses. • Faisal.Software

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

Question

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

Example:

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

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

Solution

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.

Code:

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) {
    solution(1);
    solution(3);
  }

  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("(")) {
          stack.push(c);
        } else {
          if(!stack.isEmpty()) {
            stack.pop();
          } else {
            isValid = false;
            break;
          }
        }
      }
      if (!isValid) {
        continue;
      }
      resultList.add(permutation);
    }

    System.out.println(resultList);
  }

  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) {
      if(!permutationList.contains(String.valueOf(s))){
        permutationList.add(String.valueOf(s));
      }
    }

    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: