Leetcode之回溯法专题-22. 括号生成(Generate Parentheses)

Leetcode之回溯法专题-22. 括号生成(Generate Parentheses)

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

例如,给出 n = 3,生成结果为:

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

 

分析:给定一个n,生成所有可能的括号组合。

举个例子,n=3,需要生成三个括号,那最后的长度是6,即2*n,那我们字符的数量到2*n的时候应该停下。

接下来我们写出递归函数:

    public void dfs(int n, int step, String str, int left, int right) {
        if (step == n) {
            ans.add(str);
            return;
        }
        if (left < n / 2) {
            dfs(n, step + 1, str + "(", left + 1, right);
        }
        if (left > right) {
            dfs(n, step + 1, str + ")", left, right + 1);
        }

    }

 

函数中用left存左括号的数量,right存储右括号的数量,step存现在的括号数量,n是需要括号的总数量。

 

最后的AC代码为:

class Solution {
    List<String> ans = null;
    
    
    public void dfs(int n,int step,String str,int left,int right){
        if(step == n){
            ans.add(str);
            return;
        }
        if(left<n/2){
            dfs(n,step+1,str+"(",left+1,right);
        }
        if(left>right){
            dfs(n,step+1,str+")",left,right+1);
        }
        
    }
    
    public List<String> generateParenthesis(int n) {
        ans = new ArrayList<>();
        
        
        dfs(2*n,0,"",0,0);
        return ans;
    }

    
}

 

上一篇:VBA编程图表(二十一)


下一篇:ApacheCon 首次亚洲大会火热来袭,SphereEx 邀您共赴年度盛会!