LeetCode：括号生成

题目：

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3 输出：[        "((()))",        "(()())",        "(())()",        "()(())",        "()()()"      ]

来源：力扣（LeetCode）

解：

这道题我自己是没看出什么规律，查看了官方题解也是没什么规律可循，因为不同括号的组合是任意的，所以一般用递归优化或者回溯剪枝。

这里用递归求解，那么正确序列每一次递归有两个条件， '(' 和 ')' 括号都不能超出规定对数，且已有序列中（数量） '(' >= ')' ，这样就能保证括号匹配正确。这道题简单在于只有一种括号，数量对了就可以，而不用考虑匹配顺序。

class Solution { private List<String> rs=new ArrayList<String>(); public void fc(String s, int lf, int rg){ if(lf==0 && rg==0){ rs.add(s); return; } if(lf>0){ fc(s+"(",lf-1,rg); } if(rg>0 && rg>lf){ fc(s+")",lf,rg-1); } return; } public List<String> generateParenthesis(int n) { fc("",n,n); return rs; } }