当前位置：首页 > article >正文

leetcode 括号(面试题)

article 2025/1/12 23:16:10

题目

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bracket-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解思路

如果left 以及 right都为空，那么是递归到最后，就将填充完的track返回。
如果左边还有填充，也就是左括号数量还有空余量，那么在毁掉中加入“（”，同时左边的测试-1，加入左边的括号了，那么右边与之匹配的括号也要+1.再递归。
如果右边还能填充，那么填充完右边之后，右边的剩余可以匹配的数量-1,同时增加")"
在函数调用的时候，先填入n表示左边匹配的数量，再填右边的数量0，填充的字符串为“””
每次左边递归的同一级代码必须有右递归代码，这样左边和右边就每次都是匹配的。

代码

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        backtrack(res,n,0,"");
        return res;
    }

    void backtrack(vector<string> &res,int left,int right,string track)
    {
        if(!left && !right)
        {
            res.push_back(track);
        }
        if(left>0)
        {
            backtrack(res,left-1,right+1,track+"(");
        }
        if(right>0)
        {
            backtrack(res,left,right-1,track+")");
        }
    }

};