数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
实现思想
通过观察发现，从左往右边数，左括号的个数一直大于等于右括号的个数，由此可列出循环进行排列组合。
class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); dfs(1,0,n ,res,"("); return res; } private void dfs(int l,int r,int n, List<String> res,String s) { if (s.length() == n * 2) { res.add(s); } else if (l==n){ dfs(l,r+1,n,res,s+')'); } else { if (r==l) { dfs(l+1,r,n,res,s+'('); } else { dfs(l+1,r,n,res,s+'('); dfs(l,r+1,n,res,s+')'); } } } 借助动态规划的思想，和数学归纳法类似。关键只要求出n和n+1的组合。当增加一对新的括号时，这对括号只能作为原括号的外括号或者增加到旁边这两种情况。即所有组合为括号内的组合+括号外的组合
“（” a种组合 “）” b种组合，总数为a+b种
举个例子：
用圆括号（）表示原来得到组合，方括号【】表示新加的括号 tip：只是为了表示方便，实际上（【】）和【（）】是一样的
n=2时，有（）（）和（（））
n=3时，有【（）（）】，【（（））】，【（）】（），和【】（）（），【】（（））
class Solution { public List<String> generateParenthesis(int n) { LinkedList<LinkedList<String>> result = new LinkedList<LinkedList<String>>(); if(n == 0) return new ArrayList<String>(); LinkedList<String> list0 = new LinkedList<String>(); list0.add(""); result.add(list0); LinkedList<String> list1 = new LinkedList<String>(); list1.add("()"); result.add(list1); for (int i = 2; i <= n; i++) { LinkedList<String> temp = new LinkedList<String>(); for (int j = 0; j < i; j++) { List<String> str1 = result.get(j); List<String> str2 = result.get(i - 1 - j); for (String s1 : str1) { for (String s2 : str2) { String el = "(" + s1 + ")" + s2; temp.add(el); } } } result.add(temp); } return result.get(n); } } 本网页由快兔兔AI采集器生成，目的为演示采集效果，若侵权请及时联系删除。
原文链接：https://bbs.csdn.net/skill/algorithm/algorithm-2bd98707da9f4fe1b34ab125fa4664ea