回溯算法最佳实践：括号生成

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

List<String> generateParenthesis(int n);

vector<string> generateParenthesis(int n);

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

def generateParenthesis(n: int) -> List[str]:

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

func generateParenthesis(n int) []string

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

var generateParenthesis = function(n) {};

"((()))",
"(()())",
"(())()",
"()(())",
"()()()"

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

void backtrack(int n, int i, string& track) {
    // i 代表当前的位置，共 2n 个位置
    // 穷举到最后一个位置了，得到一个长度为 2n 组合
    if (i == 2 * n) {
        print(track);
        return;
    }

    // 对于每个位置可以是左括号或者右括号两种选择
    for choice in ['(', ')'] {
        track.push(choice); // 做选择
        // 穷举下一个位置
        backtrack(n, i + 1, track);
        track.pop(choice); // 撤销选择
    }
}

// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

public List<String> generateParenthesis(int n) {
    if (n == 0) return new ArrayList<>();
    // 记录所有合法的括号组合
    List<String> res = new ArrayList<>();
    // 回溯过程中的路径
    StringBuilder track = new StringBuilder();
    // 可用的左括号和右括号数量初始化为 n
    backtrack(n, n, track, res);
    return res;
}

// 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
void backtrack(int left, int right, 
            StringBuilder track, List<String> res) {
    // 若左括号剩下的多，说明不合法
    if (right < left) return;
    // 数量小于 0 肯定是不合法的
    if (left < 0 || right < 0) return;
    // 当所有括号都恰好用完时，得到一个合法的括号组合
    if (left == 0 && right == 0) {
        res.add(track.toString());
        return;
    }
    
    // 尝试放一个左括号
    track.append('('); // 选择
    backtrack(left - 1, right, track, res);
    track.deleteCharAt(track.length() - 1); // 撤消选择

    // 尝试放一个右括号
    track.append(')'); // 选择
    backtrack(left, right - 1, track, res);
    track.deleteCharAt(track.length() - 1); // 撤消选择
}

vector<string> generateParenthesis(int n) {
    if (n == 0) return {};
    // 记录所有合法的括号组合
    vector<string> res;
    // 回溯过程中的路径
    string track;
    // 可用的左括号和右括号数量初始化为 n
    backtrack(n, n, track, res);
    return res;
}

// 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
void backtrack(int left, int right, 
            string& track, vector<string>& res) {
    // 若左括号剩下的多，说明不合法
    if (right < left) return;
    // 数量小于 0 肯定是不合法的
    if (left < 0 || right < 0) return;
    // 当所有括号都恰好用完时，得到一个合法的括号组合
    if (left == 0 && right == 0) {
        res.push_back(track);
        return;
    }
    
    // 尝试放一个左括号
    track.push_back('('); // 选择
    backtrack(left - 1, right, track, res);
    track.pop_back(); // 撤消选择

    // 尝试放一个右括号
    track.push_back(')'); // 选择
    backtrack(left, right - 1, track, res);
    track.pop_back(); // 撤消选择
}

# 注意：python 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

from typing import List

def generateParenthesis(n: int) -> List[str]:
    if n == 0: 
        return []
    # 记录所有合法的括号组合
    res = []
    # 回溯过程中的路径
    track = ''
    # 可用的左括号和右括号数量初始化为 n
    backtrack(n, n, track, res)
    return res

# 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
def backtrack(left: int, right: int, track: str, res: List[str]) -> None:
    # 若左括号剩下的多，说明不合法
    if right < left:
        return
    # 数量小于 0 肯定是不合法的
    if left < 0 or right < 0:
        return
    # 当所有括号都恰好用完时，得到一个合法的括号组合
    if left == 0 and right == 0:
        res.append(track)
        return
    
    # 尝试放一个左括号
    track += '(' # 选择
    backtrack(left - 1, right, track, res)
    track = track[:-1] # 撤消选择

    # 尝试放一个右括号
    track += ')' # 选择
    backtrack(left, right - 1, track, res)
    track = track[:-1] # 撤消选择

// 注意：go 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

func generateParenthesis(n int) []string {
    if n == 0 {
        return []string{}
    }
    res := []string{}
    // 回溯过程中的路径
    track := ""
    backtrack(n, n, &track, &res)
    return res
}

func backtrack(left, right int, track *string, res *[]string) {
    // 若右括号剩下的多，说明不合法
    if right < left {
        return
    }
    // 数量小于 0 肯定是不合法的
    if left < 0 || right < 0 {
        return
    }
    // 当所有括号都恰好用完时，得到一个合法的括号组合
    if left == 0 && right == 0 {
        *res = append(*res, *track)
        return
    }

    // 尝试放一个左括号
    *track += "(" // 选择
    backtrack(left-1, right, track, res)
    *track = (*track)[:len(*track)-1] // 撤销选择

    // 尝试放一个右括号
    *track += ")" // 选择
    backtrack(left, right-1, track, res)
    *track = (*track)[:len(*track)-1] // 撤销选择
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 cpp 代码对比查看。

/**
 * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    if (n == 0) return [];
    
    var res = [];
    var track = '';
    
    // 回溯过程
    backtrack(n, n, track, res);
    return res;
};

/**
 * @param {number} left 左括号还有几个可以使用
 * @param {number} right 当前剩余的右括号的个数
 * @param {string} track 记录从根节点到叶子节点所经过的路径
 * @param {string[]} res 记录所有合法的括号组合
 * @return {void}
 */
var backtrack = function(left, right, track, res) {
    // 若右括号剩下的多，说明不合法
    if (right < left) return;
    // 数量小于 0 肯定是不合法的
    if (left < 0 || right < 0) return;

    // 满足结束条件，加入到结果集合
    if (left == 0 && right == 0) {
        res.push(track);
        return;
    }
    
    // 尝试放一个左括号
    track = track + '('; // 选择
    backtrack(left - 1, right, track, res);
    track = track.slice(0, -1); // 撤消选择

    // 尝试放一个右括号
    track = track + ')'; // 选择
    backtrack(left, right - 1, track, res);
    track = track.slice(0, -1); // 撤消选择
};