Generate Parentheses

dfs backtracking  经验： 如果dfs函数的参数是pass by reference, 那么在递归调用后，要做恢复现场的工作，如下面函数中对com 和lcnt的操作。 如果dfs函数的参数是pass by value, 那么在递归调用后，就可以不用再作处理了，如flavor 3 中的参数。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        int lcnt=0;
        string com="";
        help(n,ret,com,lcnt);
        return ret;
    }
    void help(int n, vector<string>&ret, string&com, int &lcnt){
        if(lcnt<com.length()-lcnt||lcnt>n){
            return;
        }
        if(com.length()==2*n){
            ret.push_back(com);return;
        }
        com.push_back('(');
        lcnt++;
        help(n,ret,com,lcnt);
        com.pop_back();
        lcnt--;
        com.push_back(')');
        help(n,ret,com,lcnt);
        com.pop_back();//don't forget this!
    }
};

// flavor 2
class Solution {
public:
    vector<string> generateParenthesis(int n) {
       
        vector<string> ret;
        string com="";
        generateParenthesisRe(0,0,n,com,ret);
        return ret;
       
    }
   
    void generateParenthesisRe(int left, int right, int n,string& com,vector<string>&ret){
        if(left==n&&right==n){
            ret.push_back(com);
            return;
        }
        if(left>n||right>n)
            return;
        if(left>right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
            com.push_back(')');
            generateParenthesisRe(left,right+1,n,com,ret);
            com.pop_back();           
        }
        else if(left==right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
        }
           
    }
};

//flavor 3
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        generator(ret,"",0,0,n);
        return ret;
    } 
    void generator(vector<string> & ans, string s, int l, int r, int n){
   
        if(l>n||r>n)
            return;
        if(l==n&&r==n)
            ans.push_back(s);
        generator(ans,s+"(",l+1,r,n);
        if(l>r)
            generator(ans,s+")",l,r+1,n);
    }

};