[22]括号生成

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 回溯算法 
// 👍 1579 👎 0

/*
* 22 括号生成
* 2021-02-27 14:54:20
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        dfs(n, n, "");
        return ans;
    }

    void dfs(int left, int right, string s){
        if(left > right) return ; // 是剩余数量

        if(left == 0){
            for(int i = 0;i < right;i++)
                s += ')';
            ans.push_back(s);
        }else{
            dfs(left -1, right, s + '(');
            dfs(left, right - 1, s + ')');
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)