力扣链接：22.括号生成

难度：⭐⭐

解题关键词：回溯、字符串、递归

解题思路：递归生成括号，在终止条件中，如果左括号的数量和右括号的数量都等于了要求的数量，那么就是一个合法的组合。如果在任意时刻，组合中右括号的数量大于了左括号的数量，那么就可以直接停止递归了。

function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  backTrace(n, result, 0, 0, "");

  return result;
}

// 递归，把合法的组合都加到 result 中
// n：括号总共有多少对
// leftNum：现在左括号的数量是多少个
// rightNum：现在右括号的数量是多少个
// str：当前的扩号组合的字符串
const backTrace = (
  n: number,
  result: string[],
  leftNum: number,
  rightNum: number,
  str: string
): void => {
  // 如果数量已经达到了，那么直接加入到结果集中
  if (leftNum === rightNum && leftNum === n) {
    result.push(str);
    return;
  }

  // 如果右括号的数量大于了左括号，那么就是不合法的括号组合，直接 return 掉
  if (leftNum < rightNum) return;

  // 如果左括号数量还没有达到，继续递归
  if (leftNum < n) {
    backTrace(n, result, leftNum + 1, rightNum, str + "(");
  }

  // 如果左括号数量多，可以加右括号
  if (leftNum > rightNum) {
    backTrace(n, result, leftNum, rightNum + 1, str + ")");
  }
};