Comment on page

# 22.Generate-Parentheses

## 题目描述

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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

## 代码

### Approach 1: Brute Force

class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
private void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
}
} else {
/// looks like backtrace
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
private boolean valid(char[] current) {
int balance = 0;
for (char c : current) {
if (c == '(') {
balance++;
} else {
balance--;
}
if (balance < 0) return false;
}
return (balance == 0);
}
}

### Approach #2 Backtracking

class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int open, int close, int max) {
if (cur.length() == max * 2) {
return;
}
if (open < max) {
backtrack(ans, cur + "(", open + 1, close, max);
}
if (close < open) {
backtrack(ans, cur + ")", open, close + 1, max);
}
}
}

### Approach #3 Closure Number

class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {