Подсчет всех возможных сбалансированных двоичных строк N длины

Учитывая число N , задача состоит в том, чтобы найти общее количество возможных сбалансированных двоичных строк длины N . Двоичная строка называется сбалансированной, если:

• Количество нулей и единиц равно в каждой двоичной строке.
• Количество нулей в любом префиксе двоичных строк всегда больше или равно количеству 1
• Например: 01 — это сбалансированная двоичная строка длиной 2, а 10 — нет.

Пример:

Input: N = 4
Output: 2
Explanation: Possible balanced binary strings are: 0101, 0011

Input: N = 5
Output: 0

Подход: Данная проблема может быть решена следующим образом:

1. Если N нечетно, то сбалансированная двоичная строка невозможна, так как условие равного количества нулей и единиц не выполняется.
2. Если N четно, то двоичная строка длины N будет иметь N/2 сбалансированных пар нулей и единиц.
3. Итак, теперь попробуйте создать формулу для получения количества сбалансированных строк, когда N четно.

So if N = 2, then possible balanced binary string will be “01” only, as “00” and “11” do not have same count of 0s and 1s and “10” does not have count of 0s >= count of 1s in prefix [0, 1).
Similarly, if N=4, then possible balanced binary string will be “0101” and “0011”
For N = 6, then possible balanced binary string will be “010101”, “010011”, “001101”, “000111”, and “001011”
Now, If we consider this series:
For N=0, count(0) = 1
For N=2, count(2) = count(0)*count(0) = 1
For N=4, count(4) = count(0)*count(2) + count(2)*count(0) = 1*1 + 1*1 = 2
For N=6, count(6) = count(0)*count(4) + count(2)*count(2) + count(4)*count(0) = 1*2 + 1*1 + 2*1 = 5
For N=8, count(8) = count(0)*count(6) + count(2)*count(4) + count(4)*count(2) + count(6)*count(0) = 1*5 + 1*2 + 2*1 + 5*1 = 14
.
.
.
For N=N, count(N) = count(0)*count(N-2) + count(2)*count(N-4) + count(4)*count(N-6) + …. + count(N-6)*count(4) + count(N-4)*count(2) + count(N-2)*count(0)
which is nothing but Catalan numbers.

1. Следовательно, для любого четного N верните каталонское число для (N/2) в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)