Leetcode每日一题 —— 22. 括号生成

SomeBottle 2026-10-02 09:43 1

思路

经典回溯题，每步有两个分支：放左括号或者放右括号。如果没有 n 个左括号就还可以放左括号，而如果右括号数量小于左括号就还可以放右括号。

代码

class Solution {

public:

    vector<string> generateParenthesis(int n) {

        // 回溯题

        vector<string> res;

        string temp;

        auto dfs=[&](this auto&& self,int left,int right)->void {

            if(left==n&&right==n){

                // 正好成对了

                res.emplace_back(temp);

                return;

            }

            // 如果还能放左括号就放左括号

            if(left<n){

                temp.push_back('(');

                self(left+1,right);

                temp.pop_back();

            }

            // 接下来看能不能放右括号

            if(right<left){

                temp.push_back(')');

                self(left,right+1);

                temp.pop_back();

            }

        };

        dfs(0,0);

        return res;

    }

};

最新回复 (1)

Lvvvv 10-02 10:11

1楼

数据量小，蛮力插 () 了，也不知道为什么能过（还是dfs方法思路更清晰。

class Solution {

public:

    vector<string> generateParenthesis(int n) {

        vector<unordered_set<string>> v(n + 1,unordered_set<string>());

        v[1].insert("()");

        for(int i = 2; i <= n; i++) {

            auto s = v[i - 1];

            for(auto &subs : s) {

                for(int j = 0; j < subs.size(); j++) {

                    v[i].insert(subs.substr(0,j) + "()" + subs.substr(j));

                }

            }

        }

        return vector<string>(v[n].begin(),v[n].end());

        

    }

};

// () 

// (()) ()() 

// ((())) ()(()) (())()  ()()()  (()())

* 帖子来源Linux.do

附近帖子

↑pi 最近更新的内置 codemode 和 MCP 争议很大，我想说:
📍 Leetcode每日一题 —— 22. 括号生成
↓手上同时有 gpt 订阅和 CommandCode goat 订阅怎么流畅切换
↓【求助】mac 9008刷机教程
↓pi版本最近更新好快啊
↓（不保真）fable 5.5灰测附案例
↓cline给我路由的哪了