https://leetcode.cn/problems/generate-parentheses/description

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

思路: 递归, 满足条件有: 左括号和右括号数量之和为2*n; 递归过程中左括号数量小于n则可以加左括号DFS, 若右括号数量小于左括号则可以加右括号DFS

C#实现:

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        var res = new List<string>();
        Backtrack(res, "", 0, 0, n);
        return res;
    }

    private void Backtrack(List<string> res, string current, int leftCount, int rightCount, int maxCount){
        // 数量满足条件
        if(current.Length == 2 * maxCount) {
            res.Add(current);
            return;
        }
        // 左括号最多为n个
        if(leftCount < maxCount) {
            // 使用不可变字符串时：
            // 每次递归调用都传递新字符串：current + "(" 创建全新字符串
            // 当前层的 current 保持不变：不会被递归调用修改
            // 自动回溯：递归返回后，current 还是原来的值
            Backtrack(res, current+"(", leftCount+1, rightCount, maxCount);
        }
        // 右括号数量比左括号小时,可以添加右括号
        if(rightCount < leftCount) {
            Backtrack(res, current+")", leftCount, rightCount + 1, maxCount);
        }
    }
}