穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞括号生成

用户11305962

发布于 2025-01-13 08:33:16

3200

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目：

解析：

该题：

1.决策树：

2.代码设计：

2.1.全局变量：

2.2.

代码：

private List<String> ret;
    private int left,n,right;
    private StringBuffer path;
    public List<String> generateParenthesis(int _n) {
        n = _n;

        ret = new ArrayList<>();
        path = new StringBuffer();
        dfs();
        return ret;
    } 

    private void dfs(){
        //递归出口
        if(right == n) {
            ret.add(path.toString());
            return;
        }

        /** 
        剪枝写法:
         */ 
        
        //添加左括号
        if(left < n){
            path.append("("); left++;
            dfs();
            //回溯：恢复现场
            path.deleteCharAt(path.length()-1); left--;
        } 

        //添加右括号：右括号永远满足 <= 左括号
        if(right < left) {
            path.append(")"); right++; 
            dfs();
           //回溯：恢复现场
           path.deleteCharAt(path.length()-1); right--;
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除

private