Generate Parentheses（C++括号生成）

野性酷女 2022-11-06 10:55 119阅读 0赞

解题思路：

（1）使用回溯法，注意值传递而不是址传递

class Solution {
    public:
        bool helper(string &str) {
            int count = 0;
            for(int i=0;i<str.length();i++) {
                if(str[i]=='(') count++;
                else count--;
                if(count<0) return false;
            }
            return count==0;
        }
        
        void generateall(vector<string> &v,string str,int n,int open,int close) {
            if(str.length()==n*2 && helper(str)) v.push_back(str);
            
            if(open<n) {
                str.push_back('(');
                generateall(v,str,n,open+1,close);
                str.pop_back();
            }
            
            if(open>close) {
                str.push_back(')');
                generateall(v,str,n,open,close+1);
                str.pop_back();
            }
        }
        
        vector<string> generateParenthesis(int n) {
            vector<string> v;
            string str="";
            generateall(v,str,n,0,0);
            return v;
        }
    };

（2）排列

class Solution {
    private:
        set<string> v;
    public:
        bool judge(string &s) {
            int balance=0;
            for(int i=0;i<s.length();i++) {
                if(s[i]=='(') balance++;
                else balance--;
                if(balance<0) return false;
            }
            return true;
        }
        void helper(string &s,int l,int r) {
            if(l==r && judge(s)) {
                v.insert(s);
                return;
            } else if(l==r) return;
            
            for(int i=l;i<=r;i++) {
                if(s[i]!=s[l] || l==i) {
                    swap(s[i],s[l]);
                    helper(s,l+1,r);
                    swap(s[i],s[l]);
                }
            }
            return;
        }
        
        vector<string> generateParenthesis(int n) {
            string s="";
            for(int i=0;i<n;i++) s+='(';
            for(int i=0;i<n;i++) s+=')';
            helper(s,0,s.length()-1);
            vector<string> r;
            for(auto it=v.begin();it!=v.end();it++) {
                r.push_back(*it);
            }
            return r;
        }
    };