欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 22括号生成

程序员文章站 2022-05-20 11:42:33
...

题目

leetcode 22 括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

分析

  • 使用回溯算法进行DFS,路径的每个节点都有2个选择, ‘(’ or ‘)’
  • 终止条件: 路径上’)'的个数right 大于 '('的个数left (right > left,即右括号比左括号多,一定不会出现匹配) or '('的个数left 大于 n (left > n)
  • 解的判断条件: left == right && left == n

code

class Solution {
public:
    vector<string> result;
    void backtrace(string& tmp,int l,int r,int n){
        if(r > l || l > n) return;
        if(l == r && l == n){
            result.push_back(tmp);
            return ;
        }
        tmp.push_back('(');
        backtrace(tmp,l+1,r,n);
        *tmp.rbegin() = ')'; // 把pop_back()与push_back()合在一起
        backtrace(tmp,l,r+1,n);
        tmp.pop_back();
    }
    vector<string> generateParenthesis(int n) {
        string tmp;
        backtrace(tmp,0,0,n);
        return result;
    }
};
相关标签: leetcode解题