LeetCode 22. 括号生成

22. 括号生成

解题思路

为了保证生成括号的合法性，并不是任意状态都可以随意选择左括号或者右括号
维护左括号数量 left 和右括号数量 right ，初始状态均为0

• 只有当 left < n，当前状态可以选择左括号
• 只有当 right < left，当前状态可以选择右括号

决策树

参考代码

class Solution {
    private List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, new StringBuilder());
        return result;
    }

    private void dfs(int n, int left, int right, StringBuilder curStr) {
        if(left == n && right == n) {
            result.add(curStr.toString());
            return;
        }
        // 尝试添加左括号
        if(left < n) {
            curStr.append("(");
            dfs(n, left + 1, right, curStr);
            curStr.deleteCharAt(curStr.length() - 1);
        }

        // 尝试添加右括号
        if(right < left) {
            curStr.append(")");
            dfs(n, left, right + 1, curStr);
            curStr.deleteCharAt(curStr.length() - 1);
        }
    }
}