leetcode--22. 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:

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

利用回溯算法：

如果左右括号都达到n，则push_back

如果左括号小于n，递归添加左括号的字符串

如果右括号小于左括号，递归添加右括号的字符串

class Solution {
public:
    vector<string> ret;

    void bt(string strin, int left, int right, int n) {
            if(left == n && right == n) {
                ret.push_back(strin);
            }
            if(left < n) {
                string new_str = strin + '(';
                bt(new_str, left+1, right, n);
            }
            if(right < left) { //here, originally I use right < n && right < left, however, the first is redundant
                string new_str = strin + ')';
                bt(new_str, left, right + 1, n);
            }
    }
    
    vector<string> generateParenthesis(int n) {
        bt("", 0, 0, n);
        return ret;
    }
};