</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>
