🟡 剑指 Offer II 085. 生成匹配的括号

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

还是偷瞄了一下。官方题解很吉尔复杂。参考了评论区里一条解法，时间复杂度O(n)。

匹配的括号其实只要求从左到右不会出现右括号数量多于左括号即可。那就一个一个拼就好了。

class Solution {    List<String> res;
    private void dfs(String ans, int left, int right) {        if (left == 0 && right == 0) {            res.add(ans);            return;        }
        if (left == right) {            dfs(ans + '(', left-1, right);        } else {            if (left > 0) {                dfs(ans + '(', left-1, right);            }            dfs(ans + ')', left, right-1);        }    }
    public List<String> generateParenthesis(int n) {        res = new ArrayList<>();        dfs("", n, n);        return res;    }}