LeetCode 22括号生成

题目

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

思路一

使用递归来实现

我们往一个空的字符串里添加左右括号添加左括号条件（左括号个数小于总对数）添加右括号条件（已经添加的左括号个数大于右括号个数）当添加完括号后，将字符串加入数组中，就是一种可能了，同时终止递归 class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); if (n == 0) return res; String s = ""; generate(0, 0, n, s, res); return res; } public void generate(int left, int right, int n, String s, List<String> res) { //left，right为左右括号个数 if (left == n && right == n) { //递归终止条件 res.add(s); return; } if (left < n) { generate(left + 1, right, n, s + '(', res); } if (right < left) { generate(left, right + 1, n, s + ')', res); } } }

复杂度分析

时间复杂度：可以理解为O（2^n）,但是去除了很多的不必要的部分，实际上并不是一个完整的递归树 空间复杂度：O(n), 除了原本的答案数组外，最多需要O（2N）的递归栈空间