括号生成

LeetCode 22. 括号生成 (opens new window)

题目描述

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

示例

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解题思路

输入为n，那么该问题是一个长度为2n的字符串中的一个回溯问题，每个位置都可能是左括号或者右括号。但由于有效性这一限制，选择使用右括号时，之前已经选择的左括号数量一定要多余右括号的数量，这也是在DFS数中做了一定的剪枝。

class Solution {
    private List<String> list;
    private int n;

    public List<String> generateParenthesis(int n) {
        list = new ArrayList<>();
        this.n = n;
        backtrack(new StringBuilder(), 0, 0);
        return list;
    }

    private void backtrack(StringBuilder path, int leftBrackets, int rightBrackets){
        //递归终止条件
        if(leftBrackets == n && rightBrackets == n){
            list.add(path.toString());
            return;
        }

        //选择1：选择左括号
        if(leftBrackets < n){
            path.append('(');
            backtrack(path, leftBrackets + 1, rightBrackets);
            path.deleteCharAt(path.length() - 1);
        }

        //选择2：选择右括号
        if(rightBrackets < n && leftBrackets > rightBrackets){
            path.append(')');
            backtrack(path, leftBrackets, rightBrackets + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}