美文网首页
leetcode022-括号生成

leetcode022-括号生成

作者: 陆阳226 | 来源:发表于2020-05-04 16:38 被阅读0次

    问题描述

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

    示例:

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

    解答

    1. 第一个肯定是左括号
    2. 如果剩余有左括号,放左括号是没有任何问题的
    3. 在已经放的左括号多余右括号的情况下,也就是剩余的右括号比左括号多,才可以放右括号
    ArrayList<String> list = new ArrayList<>();
    public List<String> solution(int n) {
        dfs(n, n, "");
        return list;
    }
    
    public void dfs(int left, int right, String curStr) {
        // 左右括号都放完,方法返回
        // 最后一个肯定是右括号,所以一定是递归2返回
        // 然后一直回溯到递归1返回,然后继续递归2
        if (left == 0 && right == 0) {
            list.add(curStr);
            return;
        }
        // 递归1:有左括号就放左括号
        if (left > 0) {
            dfs(left -1, right, curStr + "(");
        }
        // 递归2:剩余的右括号更多时,可以放右括号
        if (right > left) {
            dfs(left, right - 1, curStr + ")");
        }
    }
    

    相关文章

      网友评论

          本文标题:leetcode022-括号生成

          本文链接:https://www.haomeiwen.com/subject/qrdyghtx.html