括号生成---2022/02/25

题目描述

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

解题思路

首先补充一下关于深度优先搜索与广度优先搜索的知识。
深度优先搜索相当于树的先序遍历（从根结点出发，先序遍历左子树，而后先序遍历右子树），通常使用栈的数据存储观念进行计算；广度优先搜索相当于树的层次遍历，通常使用队列的数据存储观念进行计算。

代码实现

class Solution {
    
    List<String> res=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
    
        dfs(n,n,"");
        return res;
    }

    public void dfs(int left,int right,String curStr){
    
        if(left==0&&right==0)
        {
    
            res.add(curStr);
            return;
        }
        if(left>0){
    
            dfs(left-1,right,curStr+"(");
        }
        if(right>left){
    
            dfs(left,right-1,curStr+")");
        }
    }
}

性能评估

暂时没考虑到优化的方向。