如何生成所有可能的有效括号组合？

如何生成所有可能的有效括号组合？

本文介绍一种利用栈数据结构生成所有有效括号组合的算法。该算法通过跟踪左括号和右括号的数量，确保生成的组合始终保持有效。

算法的核心思想是使用两个计数器分别记录左括号和右括号的数量。 当左括号数量小于给定数量 n 时，可以添加一个左括号；当右括号数量小于左括号数量时，可以添加一个右括号。只有当左括号和右括号数量都等于 n 时，才算生成一个有效的括号组合。

以下是一个 PHP 代码示例，演示了该算法的实现：

<?php
function generateParenthesis($n) {
    $result = [];
    $stack = [];
    $leftCount = 0;
    $rightCount = 0;

    function backtrack($leftCount, $rightCount, $stack, &$result) {
        if ($leftCount === $n && $rightCount === $n) {
            $result[] = implode('', $stack);
            return;
        }

        if ($leftCount < $n) {
            $stack[] = '(';
            backtrack($leftCount + 1, $rightCount, $stack, $result);
            array_pop($stack); // 回溯：移除最后添加的左括号
        }

        if ($rightCount < $leftCount) {
            $stack[] = ')';
            backtrack($leftCount, $rightCount + 1, $stack, $result);
            array_pop($stack); // 回溯：移除最后添加的右括号
        }
    }

    backtrack($leftCount, $rightCount, $stack, $result);
    return $result;
}

$n = 3;
$combinations = generateParenthesis($n);
foreach ($combinations as $combination) {
    echo $combination . PHP_EOL;
}
?>

运行这段代码，输出结果如下：

((()))
(()())
(())()
()(())
()()()

这个改进后的 PHP 代码使用了递归回溯的方法，更加清晰易懂，并且避免了使用位运算和字符串操作的复杂性，提高了代码的可读性和可维护性。 它直接生成有效括号组合，而无需检查无效组合。