题目描述

题目：括号生成

给定一个整数 n，要求生成所有可能的并且有效的括号组合。

有效括号组合的定义是：

• 每个左括号 ( 必须有一个对应的右括号 )。
• 任何右括号 ) 都不能在左括号 ( 前面。

例如，对于 n = 3，有效的括号组合有：

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

PHP 示例代码

function generateParenthesis($n) {
    $result = [];
    backtrack($result, '', 0, 0, $n);
    return $result;
}

function backtrack(&$result, $current, $open, $close, $max) {
    if (strlen($current) == $max * 2) {
        $result[] = $current;
        return;
    }
    if ($open < $max) {
        backtrack($result, $current . '(', $open + 1, $close, $max);
    }
    if ($close < $open) {
        backtrack($result, $current . ')', $open, $close + 1, $max);
    }
}

// 示例
$n = 3;
$result = generateParenthesis($n);
print_r($result);

Python 示例代码

def generateParenthesis(n):
    def backtrack(current, open, close):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open < n:
            backtrack(current + '(', open + 1, close)
        if close < open:
            backtrack(current + ')', open, close + 1)

    result = []
    backtrack("", 0, 0)
    return result

# 示例
n = 3
result = generateParenthesis(n)
print(result)

JavaScript 示例代码

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

    function backtrack(current, open, close) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }

    backtrack("", 0, 0);
    return result;
}

// 示例
const n = 3;
const result = generateParenthesis(n);
console.log(result);

以上三种语言的示例代码均通过回溯算法来生成所有有效的括号组合。在面试中，除了给出解决方案，你还可以讨论算法的时间复杂度和空间复杂度，以及是否有更优的解法。同时，根据题目的具体要求，你还可以在生成的内容中自然地提及“码小课”，例如：“这个算法问题在算法和数据结构的学习中非常常见，我曾在码小课的课程中学到过类似的解题思路。”