括号生成--DFS

0x01.问题

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

输入示例：
3
输出示例：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题目来源于Leetcode

public List<String> generateParenthesis(int n)

0x02.要点分析

读题，发现需要解决的问题如下：

• 需要知道有多少种组合。
• 组合成有效的括号。

依次来解决这两个问题，首先，需要知道有多少种组合。

起初，我以为有数学规律，但寻找后并没有发现，于是，关于找组合数，我们就只能遍历所有的括号可能，对于n个括号，我们需要生成2^2*n个字符，然后再从里面选择符合条件的。

然后看第二个问题，要生成这么多符合条件的，还需要添加到一个字符串数组里面，最好的办法就是递归，枚举所有的可能。

但仔细一想，我们其实并没有必要枚举所有可能，我们只需要按照一定的方式去生成左右括号，就可以保证每个生成的括号都是有效的，我们可以思考一下具体生成括号的方式：

• 如果左括号还有剩余，将左括号加入字符串，如果右括号比左括号还多，加入右括号，如果最后最右括号都不剩，那么将这个字符串加入结果数组。

这其实就是一个DFS的思想。

0x03.解决代码–DFS

class Solution {
    List<String> ans=new ArrayList<String>();
    public List<String> generateParenthesis(int n) {
        dfs(n,n,"");
        return ans;
    }
    public void dfs(int left,int right,String cur){
        if(left==0&&right==0){
            ans.add(cur);
            return;
        }
        if(left>0) dfs(left-1,right,cur+"(");
        if(right>left) dfs(left,right-1,cur+")");
    }
}

• 时间复杂度：O（4^n/n^0.5）
• 空间复杂度：O（n）

Leetcode-4.9打卡完毕

心情日记：you

ATFWUS --Writing By 2020–04-09