[LeetCode] 22. Generate Parenthe

</br>

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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

</br>

Solution

The solution to this problem can be represented as a tree, therefore, we should use backtracking to iterate all possibility while trimming down those unqualified one.

                0
                |
               '('
          /           \
       '(('           '()'
     /     \           |
  '((('    '(()'     '()('

   ...      ...       ...

The code is shown as below.

Java

public class Solution {
   public List<String> generateParenthesis(int n) {
       
       List<String> ans = new ArrayList<String>();
       
       if(n<=0)    return ans;
       
       backtrack(ans,"",0,0,n);
       return ans;
   }
   
   public void backtrack(List<String> ans, String subans, int left_num, int right_num, int max){
       
       // Reach the bottom of the tree 
       if(subans.length() == max*2 && left_num == max && right_num ==max){
           ans.add(subans);
           return;
       }   
       
       //First adding '('
       if(left_num<max){
           String sub = subans + "(";
           backtrack(ans,sub,left_num+1,right_num,max);
       }
       
       //If the number of '(' is bigger than ')', then we can add ')'
       if(left_num>right_num){
           backtrack(ans,subans+")",left_num,right_num+1,max);
       }
   }
}

From the code, we can see that the sequence of two if-sentence is pretty important, as we should first adding '(' rather than randomly adding ')' in order to keep the parentheses valid.

</br>