各位PHP朋友请求一个PHP的算法

Question

数字N代表生产括号的对数，请你设计一个函数？用于能够生产所有可能的并且有效括号组合！
示例1：
输入： N=3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例2：
输入： N=2
输出:["(())","()()"]

示例3：
输入： N=1
输出:["()"]

Answer 1

其实很简单，解题思路就是用数据结构---栈，去判断括号是不是合法。

(入栈，)出栈，如果合法,最后栈刚好出完了，不会有剩余。

<?php

function generate($n)
{
    $bit = $n * 2;
    $maxData = pow(2, $bit) - 1;
    
    for ($i=0;$i<$maxData; $i++) {
        $bin = decbin($i);
        $bin = str_pad($bin, $bit, 0, STR_PAD_LEFT);
        $arr = [];
        
        $length = strlen($bin);
        for ($j=0;$j<$length;$j++) {
            if ($bin[$j] == '0') {
                array_push($arr, 1);
            } else {
                if (is_null(array_pop($arr))) {
                    continue 2;
                }
            }
        }
        
        if (count($arr) > 0) {
            continue;
        }
        
        echo str_replace(['0', '1'], ['(', ')'], $bin) . PHP_EOL;
    }
}

generate($argv[1]);

在终端命令输入。

 php test.php 3