回溯法
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n <= 0)
return ans;
generate(new StringBuilder(), 0, 0, n, ans);
return ans;
}
private void generate(StringBuilder currString, int left, int right, int max, List<String> ans) {
if (currString.length() == max * 2) {
ans.add(currString.toString());
return ;
}
if (left < max) { // 能够继续添加左括号
currString.append('(');
generate(currString, left + 1, right, max, ans);
currString.deleteCharAt(currString.length() - 1);
}
if (right < left) { // 能够添加有括号
currString.append(')');
generate(currString, left, right + 1, max, ans);
currString.deleteCharAt(currString.length() - 1);
}
}
}
蛮力法
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n <= 0)
return ans;
generate(new char[2 * n], 0, ans);
return ans;
}
private void generate(char[] currentString, int pos, List<String> ans) {
if (pos == currentString.length) {
if (valid(currentString))
ans.add(new String(currentString));
} else {
currentString[pos] = '(';
generate(currentString, pos + 1, ans);
currentString[pos] = ')';
generate(currentString, pos + 1, ans);
}
}
private boolean valid(char[] currentString) {
int balance = 0;
for (char ch : currentString) {
if (ch == '(')
++balance;
else
--balance;
if (balance < 0)
return false;
}
if (balance == 0)
return true;
return false;
}
}