22. Generate Parentheses

DescriptionHintsSubmissionsDiscussSolution

Pick One

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:

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

和上一个

leetcode17Letter Combinations of a Phone Number【队列】 - CSDN博客 

写法灰常相似啊

维护一个队列，每次取出一个，判断是否个数，在最后加入不同括号，入队列

最后一位特判

很愚蠢的是 以为是Python语法 上来CE了

再就是当时就觉得 不设定num变量 直接for(int j=0;j<ans.size();j++) 就死循环了 想了半天才明白咋回事

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>ans;
        ans.push_back("");
        for(int i=0;i<n*2;i++){
            int num=ans.size();
            for(int j=0;j<num;j++){
                string nw=ans[0];
                ans.erase(ans.begin());
                int l=0,r=0;
                for(int k=0;k<i;k++){
                    if(nw[k]=='(')
                        l++;
                    else
                        r++;
                }
                if(i!=n*2-1)
                {
                    if(l>r){
                        ans.push_back(nw+'(');
                        ans.push_back(nw+')');
                    }
                    else if(l==r)
                        ans.push_back(nw+'(');
                }
                else
                {
                    if(l==r+1)
                        ans.push_back(nw+')');
                }
            }
        }
        return ans;
    }
};