lintcode--生成括号

题目描述：
给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。

样例：
给定 n = 3, 可生成的组合如下:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路讲解：
我们首先看一下n=1、2、3时组合的结果：
当n=1,”()”
当n=2,”()()”、”(())”
当n=3,”((()))”, “(()())”, “(())()”, “()(())”, “()()()”
我们可以发现2是在1的基础上添加的”()”，可以在前面、中间、后面添加，得到的结果是”()()”、”(())”、”()()”，这个时候我们去重就可以得到n=2时，组合结果是”()()”、”(())”。同样我们通过n=2的结果，得到n=3的结果”()()()”、”(())()”、”()()()”、”()(())”、”()()()”、”()(())”、”(()())”、”((()))”、”(()())”、”(())()”,然后去重就得到了”((()))”, “(()())”, “(())()”, “()(())”, “()()()”，这就是n=3的组合结果了。这样我们就可以一步步的迭代得到我们想要的结果。这里去重是使用vector中的unique函数。

代码详解：

class Solution {
public:
    /*
     * @param n: n pairs
     * @return: All combinations of well-formed parentheses
     */
    vector<string> generateParenthesis(int n) {
        // write your code here
        vector<vector<string>>res(n);
        res[0].push_back("()");
        if(n==1){
            return res[0];
        }

        for(int i=1;i<n;i++)
        {
            int len=res[i-1].size();
            cout<<len<<endl;
            for(int j=0;j<len;j++)
            {
                int strlen1=res[i-1][j].length();
                cout<<strlen1<<endl;
                for(int k=0;k<strlen1;k++){
                    string s1=res[i-1][j].substr(0,k-0);//添加括号位置的前面的字符串
                    string s2=res[i-1][j].substr(k,strlen1-k);//添加括号位置的后面的字符串
                    string s=s1+"()"+s2;
                    //cout<<"1111 "<<s<<endl;
                    res[i].push_back(s);
                }
                res[i].push_back(res[i-1][j]+"()");
            }
            printvector(res[i]);
            sort(res[i].begin(),res[i].end());//排序
            res[i].erase(unique(res[i].begin(),res[i].end()),res[i].end());//去重
        }
        return res[n-1];
    }
    void printvector(vector<string>res)
    {
        for(int i=0;i<res.size();i++)
        {
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }
};