括号生成

原题链接

使用的方法

回溯算法

解题思路

• 给定一个整数 n，生成所有由 n 对括号组成的有效括号组合。有效括号组合是指每个左括号都有一个对应的右括号，并且左括号必须在对应的右括号之前。
• 我们可以使用回溯算法来生成所有可能的括号组合。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过递归地构建括号组合来生成所有的组合。
• 我们从空字符串开始，逐步添加左括号和右括号来构建括号组合。在每一步，我们有两个选择：要么添加一个左括号，要么添加一个右括号。我们需要确保在添加右括号之前已经添加了相应数量的左括号，以保持括号的有效性。
• 递归的终止条件是当我们处理到字符串的长度达到 2 * n 时，我们将当前的括号组合添加到结果列表中。通过这种方式，我们可以生成所有可能的括号组合，并最终返回结果列表。

代码实现

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] path = new char[n * 2];
        dfs(0,0,n,path,res);
        return res;
    }

    public void dfs(int left,int right,int n,char[] path ,List<String> res){
        if(right == n){
            res.add(new String(path));
            return;
        }
        if(left < n){
            path[left+right] = '(';
            dfs(left+1,right,n,path,res);
        }
        if(right < left){
            path[left + right] = ')';
            dfs(left,right+1,n,path,res);
        }
    }
}