题目：括号生成

使用到的是回溯算法

对于输入的数字n，可以知道的是最终的元素为2n个括号，其中左括号和右括号都为n个

先经过一次分析得到规律：以n=2为例，每个元素分别有2个左右括号，第一个空必须是’ （ ’，此时left的数量加一；而第二个空则有两种可能，当为‘（’时，left的数量已经达到了2，那么之后两个空就只能是‘）’；当为‘）’时，此时left = right，第三个空就只能是‘（’，从而得出第四个空是‘）’

总结规律，可以得出：

1.当left < n时，应该添加‘（’

2.当right < left时，应当有‘）’与其配对，故添加‘）’

在此条件下进行递归，最后当left+right与n相同时终止最后一层递归，返回上一层的枝，继续下一个子节点的递归

generateParenthesis()

 1class Solution
 2{
 3public:
 4    vector<string> generateParenthesis(int n)
 5    {
 6        std::vector<string> combinations;
 7        string combination;
 8        backTrace(0, 0, combination, combinations, n);
 9        return combinations;
10    }
11
12private :
13    void backTrace(int left, int right, string& combination, std::vector<string>& combinations, int n)
14    {
15        if(left + right == 2 * n)
16        {
17            combinations.push_back(combination);
18            return;
19        }
20        else
21        {
22            if(left < n)
23            {
24                combination.push_back('(');
25                backTrace(left + 1, right, combination, combinations, n);
26                combination.pop_back();
27            }
28            if(right < left)
29            {
30                combination.push_back(')');
31                backTrace(left, right + 1, combination, combinations, n);
32                combination.pop_back();
33            }
34        }
35    }
36};

来源：语雀原笔记