Balanced Bracket Count
Hard · rating 1850 · Dynamic Programming, Combinatorics
Read n and print the number of distinct balanced sequences of n pairs of parentheses (the n-th Catalan number).
Constraints: 0 ≤ n ≤ 200
Editorial
Approach
The number of balanced sequences of n bracket pairs is the n-th Catalan number. Build it with the classic recurrence: fixing where the first bracket closes splits the rest into two independent balanced sequences, giving C(n) = Σ C(i)·C(n-1-i).
dp[0] = 1
for i in range(1, n+1):
dp[i] = sum(dp[j] * dp[i-1-j] for j in range(i))Complexity
Time: O(n²) (big integers). Space: O(n).
Related problems
- Dice Sum Ways — Medium
- Unique Grid Paths — Hard
- Equal Subset Partition — Hard
- K-th Permutation — Hard
- Treasure Grid — Hard
- Word Break — Hard