每天进步一点点🤏

括号生成

  • ~1.93K 字

括号生成

题目

1
2
3
4
5
6
7
8
9
10
11
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

提示：1 <= n <= 8

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
思路:
将'()'作为一个整体str
n=1时,返回['()']
n=2时,将str插入'()'字符串的0和1位置,结果为['()()','(())']
n=3时,将str插入n=2时生成的数组['()()','(())']中的字符串中0,1,2位置
依次递归,结果去重

代码:
function generateParenthesis($num)
{
    if ($num == 1) {
        return ['()'];
    }

    $result = [];

    //获取$num-1次递归的数组
    $data = $this->generateParenthesis($num - 1);

    foreach ($data as $item) {
        for ($i = 0; $i < $num; $i++) {
            //将'()'字符串插入$num-1次递归数组的0~$num-1的位置
            $result[] = substr($item, 0, $i) . '()' . substr($item, $i);
        }
    }

    //去重
    return array_values(array_unique($result));
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
思路:
合法的括号生成过程必然是'('数量大于等于的')',每次新增'('进入下一次递归,直到'('的数量等于请求的数量,
如果')'的数量小于'('的数量,则允许新增一个')',直到')'的数量达到请求的数量为止

代码:
function generateParenthesis($n)
{
    $res = [];
    $this->backtrack($n, '', 0, 0, $res);

    return $res;
}

function backtrack($n, $cur, $open, $close, &$res)
{
    if (strlen($cur) == $n * 2) {
        $res[] = $cur;

        return;
    }

    if ($open < $n) {
        //如果'('数量小于$n,加一个'(',进入下一次递归,每次都会新增,直到满足'('数量为止
        $this->backtrack($n, $cur . '(', $open + 1, $close, $res);
    }

    if ($close < $open) {
        //如果')'的数量小于'('的数量,加一个')',允许进入下一次递归,产生分支
        $this->backtrack($n, $cur . ')', $open, $close + 1, $res);
    }
}