CC128 括号生成

素颜马尾好姑娘i 2023-10-04 17:54 13阅读 0赞

### 描述 ###

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：1 \\le n \\le 81≤n≤8

### 示例1 ###

输入：

复制返回值：

["()"]

复制

### 示例2 ###

输入：

复制返回值：

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

#include <stdio.h>
    
    /*
    Write a function Brackets(int n) that prints all combinations of well-
    formed brackets. For Brackets(3) the output would be ((())) (()()) (())
    () ()(()) ()()()
    
    You can approach this the same way you'd do it by hand.  Build up the
    string of brackets left to right.  For each position, you have a
    decision of either ( or ) bracket except for two constraints:
    (1) if you've already decided to use n left brackets, then you can't
    use a another left bracket and
    (2) if you've already used as many right as left brackets, then you
    can't use another right one.
    
    This suggests the following alorithm. Showing what happens on the
    stack is a silly activity.
    */
    
    // Buffer for strings of ().
    char buf[1000];
    
    // Continue the printing of bracket strings.
    //   need is the number of ('s still needed in our string.
    //   open is tne number of ('s already used _without_ a matching ).
    //   tail is the buffer location to place the next ) or (.
    void cont(int need, int open, int tail)
    {
        // If nothing needed or open, we're done.  Print.
        if (need == 0 && open == 0) {
            printf("%s\n", buf);
            return;
        }
    
        // If still a need for (, add a ( and continue.
        if (need > 0) {
            buf[tail] = '(';
            cont(need - 1, open + 1, tail + 1);
        }
    
        // If still an open (, add a ) and continue.
        if (open > 0) {
            buf[tail] = ')';
            cont(need, open - 1, tail + 1);
        }
    }
    
    void Brackets(int n)
    {
        cont(n, 0, 0);
    }
    
    int main(void)
    {
        Brackets(4);
        return 0;
    }