題設(shè)
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
要點(diǎn)
- 回溯 backtracking
- 剪枝
明顯地，可以用回溯法來(lái)解鼠锈。判斷條件為：
leftCount:左括號(hào)數(shù)
rightCount：右括號(hào)數(shù)
str: 記錄生成的括號(hào)串
leftCount > n => 不可能有解闪檬，剪枝
rightCount > leftCount => 不可能有解，剪枝
str.length() == n * 2：得到一個(gè)解
回溯法在每一步购笆，本來(lái)應(yīng)該用for循環(huán)粗悯，枚舉此次所有可能的情況，如八皇后的棋盤列數(shù)同欠。但是這里只有加左括號(hào)和右括號(hào)兩種样傍，直接寫就可以了。
代碼：
public List<String> generateParenthesis(int n){
List<String> list = new ArrayList<String>();
if(n == 0)
return list;
backTrack(list , n , 0 , 0 , "");
return list;
}
/*
leftCount:左括號(hào)數(shù)
rightCount：右括號(hào)數(shù)
str: 記錄生成的括號(hào)串
leftCount > n => 不可能有解铺遂，剪枝
rightCount > leftCount => 不可能有解衫哥，剪枝
str.length() == n * 2：得到一個(gè)解
*/
public void backTrack(List<String> list , int n , int leftCount , int rightCount , String str){
// 剪枝
if(leftCount > n)
return;
if(rightCount > leftCount)
return;
// 找到正確答案
if(str.length() == n * 2){
list.add(str);
return;
}
// 這里本來(lái)應(yīng)該用for循環(huán)，枚舉此次所有可能的情況襟锐，如八皇后的棋盤列數(shù)撤逢。但是這里只有加左括號(hào)和右括號(hào)兩種，直接寫就可以了
// 左括號(hào)的情況
str += '(';
int newLeftCount = leftCount + 1;
backTrack(list , n , newLeftCount , rightCount , str);
// 回溯
str = str.substring(0 , str.length() - 1);
// 右括號(hào)的情況
str += ')';
if(str.length() == 1)// 第一位不可能是')'
return;
int newRightCount = rightCount + 1;
backTrack(list , n , leftCount , newRightCount , str);
}
