Description
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:
代码语言：javascript复制[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]Solution
代码语言：javascript复制package com.dylan.leetcode;
import java.util.LinkedList;
import java.util.List;
import org.junit.Test;
/**
* Created by liufengquan on 2018/8/1.
*/
public class GenerateParentheses {
List<String> strings = new LinkedList<>();
public List<String> generateParenthesis(int n) {
generate(new StringBuilder(), n, n);
return strings;
}
private void generate(StringBuilder sb, int left, int right) {
if (left == 0) {
StringBuilder stringBuilder = new StringBuilder(sb);
while (right > 0) {
stringBuilder.append(")");
right--;
}
strings.add(stringBuilder.toString());
return;
}
if (right > left) {
sb.append(")");
generate(sb, left, right -1);
sb.deleteCharAt(sb.length() - 1);
}
sb.append("(");
generate(sb, left - 1, right);
sb.deleteCharAt(sb.length() - 1);
}
@Test
public void test() {
List<String> list = generateParenthesis(3);
printList(list);
}
private void printList(List<String> list) {
for (String s : list) {
System.out.println(s);
}
System.out.println();
}
}
