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

``````import java.util.*;

/**
* Created by gzdaijie on 16/5/19
* 递归解法,tmp记录构造的字符串
*/
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
StringBuilder tmp = new StringBuilder();
recursionGenerate(result, tmp, n, n);
return result;
}

/**
* 递归构造组合方式
* @param result 记录结果
* @param tmp 记录临时组合的字符串
* @param left 记录左括号剩余个数
* @param right 记录右括号剩余个数
*/
private void recursionGenerate(List<String> result, StringBuilder tmp, int left, int right) {
if (left == 0 && right == 0) {
return;
}
// 还有剩余的左括号,添加左括号递归
if (left > 0) {
tmp.append('(');
recursionGenerate(result, tmp, left - 1, right);
tmp.setLength(tmp.length() - 1);
}
// 还有剩余的右括号,且剩余的右括号多于左括号,添加右括号递归
if (right > 0 && left < right) {
tmp.append(')');
recursionGenerate(result, tmp, left, right - 1);
tmp.setLength(tmp.length() - 1);
}
}
}
``````
updated 2016-05-19 09:37:58