InternDoor

Every balanced string of brackets

Mediumbacktracking · recursion · strings

Reported in interviews at (where)

A string of ( and ) is balanced when it has as many of each and, reading left to right, the closing brackets never outnumber the opening ones so far.

Return every balanced string with exactly n opening and n closing brackets, in sorted order, where ( comes before ).

Example 1
Input
n = 2
Output
["(())","()()"]

Of the six strings with two of each bracket, only these two never close more than they have opened.

Example 2
Input
n = 1
Output
["()"]

With one pair there is only one way.

Limits

  • 1 <= n <= 9

Hints

Hint 1

Build the string one bracket at a time. You may add ( while fewer than n are open, and ) while there are fewer closes than opens.

Hint 2

Trying ( before ) at every step produces the strings already in sorted order.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.