• 题目：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);
    }
}

提交结果

Github地址

LeetCode-22 括号生成

参考链接

括号生成

更多文章，请扫描二维码关注『算法半岛』