leetcode 22. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

1. 要把这个当成下棋，左括号为黑，右括号为白，则转换为：3黑3白有几种排列方式
2. 每一步都有两个选择：下黑或者下白，但是场上下白子时剩下的黑子必须比剩下的白子多
3. 比n=2时，有黑白黑白，黑黑白白
4. 变成回溯法下棋

code

class Solution {
public:
    void helper(vector <string> &str,string s,int left,int right){
        if(left==0&&right==0){
            str.push_back(s);
            return;
        }
        if(left>0)
            helper(str,s+"(",left-1,right);
        if(left<right)
            helper(str,s+")",left,right-1);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> v;
        helper(v,"",n,n);
        return v;
    }
};