LeetCode-22括号生成

> 题目：22. 括号生成

> 难度：中等

> 分类：字符串

> 解决方案：链表的遍历

今天我们学习第22题括号生成，这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

给出 n代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n=3，生成结果为：

[  "((()))",  "(()())",  "(())()",  "()(())",  "()()()"]

分析

这个题是递归方面的题，对于递归不太熟悉的小伙伴可以扫描文章下方的二维码，关注『 算法半岛』回复『 数据结构目录』，即可获得相关学习资料。

对于递归的问题，我们需要明白以下三点：

• 一个问题的解可以分解为几个子问题的解：对于这个括号生成的题，当 n=3时问题的解可以分成 n=2时问题的解；
• 子问题除了数据规模不同，求解思路完全一样：对于这个括号生成的题，当 n=3时问题的解的解思路和 n=2时问题的解的解思路完全一样，只是问题规模减小了；
• 必须存在递归终止条件：对于这个括号生成的题，我们需要使用两个变量 left和 right来记录可使用的左括号数和右括号数，如当 n=3时，初始化 left=3和 right=3，当 left>right时说明可以使用的左括号数大于可以使用的右括号数，即已经使用的右括号数比左括号数多，则会出现无效的括号对数，因此 left>right可作为本题的递归终止条件。还有当 left<0 或right<0也是递归终止条件。

上述分析所对应的 java代码如下所示：

class Solution {
    public List<String> generateParenthesis(int n) {        List<String> res = new ArrayList<String>();        helper(n, n, "", res);        return res;    }
    // 递归辅助函数    private void helper(int left, int right, String out, List<String> res){        // 递归终止条件        if (left < 0 || right < 0 || left > right)            return ;        // 当left和right都为0时，保存有效的括号组        if(left == 0 && right == 0){            res.add(out);            return ;        }
        // 减小问题的规模        helper(left-1, right, out + "(", res);        helper(left, right-1, out + ")",res);    }}

执行用时 : 2 ms, 在Generate Parentheses的Java提交中击败了94.93% 的用户

内存消耗 : 35.7 MB, 在Generate Parentheses的Java提交中击败了100.00% 的用户

Github地址

LeetCode-22 括号生成：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A22_GenerateParentheses.java

参考链接

括号生成：https://leetcode-cn.com/problems/generate-parentheses/