22.Generate-Parentheses

้ข็ฎๅฐๅ

https://leetcode.com/problems/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) {
} else {
for (int c = 0; c < n; c++) {
for (String left: generateParenthesis(c)) {
for (String right: generateParenthesis(n - 1- c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
return ans;
}
}``````

Last updated