Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Generate Parentheses

Leetcode algorithms 第 22 题:Generate Parentheses。

题目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

解答

找出n组括号的所有合法组合方式。使用递归进行,每次选择放置左括号或者右括号,当左括号放完时,剩下的即为右括号,不需要再继续递归。

但是注意不能使得括号的组合不能正确地匹配,这要求右括号不能随意摆放,如果当前左括号数量和右括号数量相等,说明已经匹配了,如果再添加一个右括号则必定导致不能匹配,因为右括号不能放在第一个,于是只有当剩余右括号数量大于左括号数量时才可以选择放置右括号。

具体代码如下:

class Solution {
public:
    void f(int x, int n1, int n2, vector<char> &s, vector<string> &ans, int n)
    {//当前位置,左括号剩余数量,右括号剩余数量,当前摆放方式,答案,括号的组数
        if (n1 == 0) //左括号剩余个数为0
        {
            string tem;
            for (int i = 0; i < x; i++) tem += s[i];
            for (int i = x; i < n; i++) tem += ')';
            ans.push_back(tem);
            return;
        }
        
        s[x] = '('; f(x+1, n1-1, n2, s, ans, n);    //放左括号
        if (n1 < n2) //剩余左括号和右括号不等时才能添加右括号
        {
            s[x] = ')'; f(x+1, n1, n2-1, s, ans, n);//放右括号
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<char> s(2*n);
        vector<string> ans;
        f(0, n, n, s, ans, 2*n);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论