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:
"((()))", "(()())", "(())()", "()(())", "()()()"
题目大意：给定括号数，找出所有合法的排列序。
思路：括号数为n，左右括号数为n，左右括号数为2n。从1到2n的合法排列满足：左括号数大于等于右括号数。假设在第K个位置处，剩余左括号数为leftNum，剩余右括号数为rightNum，则如果leftNum>0，可以放置左括号。如果rightNum > leftNum，则可以放置右括号。当leftNum与rightNum 相等时，说明找到一个合法序列。
代码：
public class Solution { public List<String> generateParenthesis(int n) { ArrayList<String> results = new ArrayList<>(); generate(n-1, n, "(", results); return results; } /** * 根据括号数递归生成合法序列 * @param leftNum 剩余左括号数 * @param rightNum 剩余右括号数 * @param s 当前序列的字符串 * @param results 结果集 */ private void generate(int leftNum, int rightNum, String s , ArrayList results) { if (leftNum == 0 && rightNum == 0) {//找到一个序列 results.add(s); } if (leftNum > 0) {//放置左括号 generate(leftNum-1, rightNum, s+"(", results); } //放置右括号 if (rightNum > 0 && leftNum < rightNum) { generate(leftNum, rightNum-1, s+")", results); } } }
