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:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]
Subscribe to see which companies asked this question.
題目
給定 n 對括號像寒，請寫一個函數(shù)以將其生成新的括號組合未妹，并返回所有組合結(jié)果逾柿。
樣例
給定 n = 3, 可生成的組合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"
分析
針對一個長度為2n的合法排列备韧，第1到2n個位置都滿足如下規(guī)則：左括號的個數(shù)大于等于右括號的個數(shù)磺浙。所以，我們就可以按照這個規(guī)則去打印括號：假設(shè)在位置k我們還剩余l(xiāng)eft個左括號和right個右括號抵窒，如果left>0丑孩，則我們可以直接打印左括號，而不違背規(guī)則火本。能否打印右括號危队，我們還必須驗(yàn)證left和right的值是否滿足規(guī)則蓄喇，如果left>=right，則我們不能打印右括號交掏，因?yàn)榇蛴`背合法排列的規(guī)則妆偏，否則可以打印右括號。如果left和right均為零盅弛，則說明我們已經(jīng)完成一個合法排列钱骂，可以將其打印出來。通過深搜挪鹏，我們可以很快地解決問題见秽，針對n=2，問題的解空間如下
代碼
public class Solution {
/**
* @param n n pairs
* @return All combinations of well-formed parentheses
*/
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> result = new ArrayList<String>();
if (n <= 0) {
return result;
}
helper(result, "", n, n);
return result;
}
public void helper(ArrayList<String> result,
String paren, // current paren
int left, // how many left paren we need to add
int right) { // how many right paren we need to add
if (left == 0 && right == 0) {
result.add(paren);
return;
}
if (left > 0) {
helper(result, paren + "(", left - 1, right);
}
if (right > 0 && left < right) {
helper(result, paren + ")", left, right - 1);
}
}
}
