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

For example, given n = 3, a solution set is:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

public class Solution {
  public List<String> generateParenthesis(int n) {

  }
}

This problem is selected from LeetCode.

Solution

We can convert the problem as follows:

find all the combinations of n “(” and n “)” such that for any point in a combination, the number of “)” is less than or equal to the
number of “(“. With this condition, we could solve the problem by recursion. Setup two variables left and right to track the number of
“(” and “)” still available. If left is greater than 0, we could add more “(“. If right is greater than left, we could add more “)”. When
right and left are all equal to 0, a complete combination is found.

public class Solution {
  public List<String> generateParenthesis(int n) {
    List<String> result = new LinkedList<>();
    generate(result, "", n, n);
    
    return result;
  }
  
  public void generate(List<String> result, String combination, int left, int right) {
    if(left == 0 && right == 0)
      result.add(combination);
    
    if(left>0) 
      generate(result, combination+"(", left-1, right);
    
    if(right > left) 
      generate(result, combination+")", left, right-1);
          
  }
}

RelatedPost