All Balanced Bracket Strings

Medium

A string of round brackets is balanced if its brackets can be matched into opening–closing pairs, each opening bracket to the left of its partner, with pairs either nested or side by side. In other words, no prefix has more closing brackets than opening ones, and the whole string has equally many of each. Given a number pairs, return every balanced string made of exactly pairs opening and pairs closing brackets, in any order.

Example 1

pairs=2 → ['(())', '()()']

Two pairs give exactly two balanced strings: (()) and ()().

Example 2

pairs=3 → ['((()))', '(()())', '(())()', '()(())', '()()()']

Five strings: ((())), (()()), (())(), ()(()), ()()(). Something like ())(() does not count: after the third character there are more closing brackets than opening ones.

Example 3

pairs=1 → ['()']

Constraints

1 ≤ pairs ≤ 8

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Backtracking

Similar problems

Cutting a Word Into Palindromes Medium Two Disjoint Palindromic Picks Medium Binary String Made of Powers of Five Medium Every Way to Space the Words Hard Best Word Set From Tiles Hard

Input

pairs=2

Expected

['(())', '()()']

Run checks the first 3 tests in your browser. Submit checks all 11 tests on the server, hidden ones included.