Подсчет числа

Question

У меня есть код, который генерирует все возможные правильные строки сбалансированных скобок. Поэтому, если входное значение равно n = 4, в строке должно быть 4 скобки, и поэтому ответы, которые даст код: {} {} и {{}}.

Теперь, что я хотел бы сделатьвывести количество возможных строк. Например, для n = 4 результат будет 2.

Учитывая мой код, возможно ли это и как я могу это сделать?

Answer 1

Просто введите счетчик.

// Change prototype to return the counter
int findBalanced(int p,int n,int o,int c)
{
    static char str[100];

    // The counter
    static int count = 0;
    if (c == n) {
        // Increment it on every printout
        count ++;
        printf("%s\n", str);
        // Just return zero. This is not used anyway and will give
        // Correct result for n=0
        return 0;
    } else {
        if (o > c) {
            str[p] = ')';
            findBalanced(p + 1, n, o, c + 1);
        }
        if (o < n) {
            str[p] = '(';
            findBalanced(p + 1, n, o + 1, c);
        }
    }
    // Return it
    return count;
}

Answer 2

То, что вы ищете, это n-тый каталонский номер . Вам нужно будет ввести биномиальный коэффициент , чтобы вычислить его, но это почти все.