力扣第22题-括号生成

题目描述

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

样例

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

示例 2：
输入：n = 1
输出：["()"]

题目评估

知识点：字符串、动态规划、回溯、深度优先遍历、广度优先遍历
难度：中等

分析

使用深度优先遍历进行剪枝递归

Java代码题解

import java.util.LinkedList;
import java.util.List;

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        generate("", n, n, res);
        return res;
    }

    /**
     * dfs
     * @param current 当前节点
     * @param left 左括号剩余
     * @param right 右括号剩余
     * @param result 结果集
     */
    private void generate(String current, int left, int right, List<String> result) {
        // 叶子节点
        if (left == 0 && right == 0) {
            result.add(current);
            return;
        }
        // 剪纸：右括号不可以剩得多
        if (right < left) {
            return;
        }
        // 遍历左子树
        if (left > 0) {
            generate(current + "(", left - 1, right, result);
        }
        // 遍历右子树
        if (right > 0) {
            generate(current + ")", left, right - 1, result);
        }
    }
}

复杂度分析

时间复杂度：O(2²ⁿ)
空间复杂度：O(2n)