原题为：
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:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

这题是一道经典的回溯题。我开始想错了思路，以为可以先把所有string初始化为((…(())…))的形式，即n个‘(’后接n个’)‘。然后把忽略掉最开头的’(‘和最后面的’)‘，让中间的n-1个‘(’和’)'挨个替换。这个方法对n=2,3是可以的，到n=4就不对了–只能返回10个string,但正确答案是14个string。代码可参考注释掉的部分。错误原因是只考虑了1,1对调的情形，但还有2,2对调，3,3对调…等等。

用回溯法想通了就比较简单。要多加练习。

#include <iostream>
#include <string>
#include <vector>

using namespace std;
#if 0
vector<string> generateParenthesis(int n) {

    vector<string> result((n-1)*(n-1)+1, string(n,'(')+string(n,')'));
    int i=0, j=0;
    while(i<(n-1)*(n-1)) {
        int index=i+1;
        for (j=0; j<n-1; j++) {
            int pos=(index%(n-1))? (index/(n-1)+1) : index/(n-1);
            swap(result[index][pos], result[index][j+n]);
            index++;
        }

        i+=n-1;
    }

    return result;
}
#endif // 0

void helper(string &currStr, vector<string> &sol, int n, int left, int right) {
    if (left==n && right==n) {
        sol.push_back(currStr);
        return;
    }
    
    if (left<n) {
        currStr+='(';
        helper(currStr, sol, n, left+1, right);
        currStr.resize(currStr.size()-1);
    }

    if (right<left) {
        currStr+=')';
        helper(currStr, sol, n, left, right+1);
        currStr.resize(currStr.size()-1);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> sol;
    string currStr;
    helper(currStr, sol, n, 0, 0);
    return sol;
}

int main()
{
    vector<string> strs=generateParenthesis(4);
    for (auto s : strs)
        cout<<s<<endl;
    return 0;
}

解法2：
分治法。假定左边部分已经至少有一个括号了，那么A就是generateParenthesis( i - 1 )，右边部分就是generateParenthesis( n - i )。这是加法原理。
下面的两个for循环嵌套是A组里面的每个元素和B组里面的每个元素粘在一起，也就是说，A里面的元素和B里面的元素各自单独都是合法的括号串，只是+在一起而已。
unordered_map就是减枝。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if (n == 0) return {""};   //注意这里不是{}
        if (mp.find(n) != mp.end()) return mp[n];
        for (int i = 1; i <= n; i++)
        {
            vector<string> A = generateParenthesis( i - 1 );
            vector<string> B = generateParenthesis( n - i );

            for (auto &a : A)
            {
                for (auto &b : B)
                {
                    string res = "(" + a + ")" + b;
                    //cout << " res = " << res << endl;
                    result.push_back(res);
                }
            }
        }
        mp[n] = result;
        return result;
    }
private:
    unordered_map<int, vector<string>> mp;
};