[LeetCode] 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:

"((()))", "(()())", "(())()", "()(())", "()()()"

DFS Solution:

class Solution {
public:
    void generate(vector<string> & res, string one, 
                  int left, int right, int n)
    {
        if(left == n && right == n)
        {
            res.push_back(one);
            return;
        }
        if(left < n)
        {
            generate(res, one+'(', left+1,right, n);
        }
        if(left > right)
        {
            generate(res, one +')', left,right+1, n);
        }
    }

    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        generate(res, "", 0,0,n);
        return res;
    }
};

BFS Solution :
find the last occurrence position P of '(' in the previous result, and append '(' + the rest + ')' to it from P+1 to end;

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        res.push_back("");
        for(int i=0;i<n;i++)
        {
            vector<string> tmp;
            for(int j=0;j<res.size();j++)
            {
                int pos = res[j].rfind('(');
                for(int k=pos+1;k<=res[j].size();k++)
                {
                    tmp.push_back(res[j].substr(0,k) +
                        '(' + res[j].substr(k) + ')');
                }
            }
            res = tmp;
        }
        return res;
    }
};