leetcode-22 Generate Parentheses

題意: 給定一數字n, 求出由n個左括弧和n個右括弧所形成的所有合理序列

解題思路: 其實這題一開始看到蠻傻眼的,後來想了想,如何才能合乎規則呢,也就是從頭開始的所有子字串(substring),其中的左括弧數量都要大於等於右括弧數量,當然,我們還要確保左右括弧數量都小於等於n,其實就類似高中排列組合的一路領先問題,所以我們每次都從右邊加括弧,並確保規則成立

code如下:

class Solution {
public:
    vector<string> ans;
   
    vector<string> generateParenthesis(int n) {
        generate("(",2*n,1,0);
        return ans;
    }
    
    void generate(string s,int total,int left,int right)
    {
        if(s.length()==total)
            ans.push_back(s);
        
        else if(s.length()<total)
        {
            if(left>=right)
            {
                if(left<total/2)
                    generate(s+"(",total,left+1,right);
                if(left>right)
                    generate(s+")",total,left,right+1);
            }
        }
       
    }
};