# Daily Challenge #101 - Parentheses Generator

### dev.to staff ・1 min read

Daily Challenge (137 Part Series)

1) Daily Challenge #1 - String Peeler
2) Daily Challenge #2 - String Diamond
3 ... 135
3) Daily Challenge #3 - Vowel Counter
4) Daily Challenge #4 - Checkbook Balancing
5) Daily Challenge #5 - Ten Minute Walk
6) Daily Challenge #6 - Grandma and her friends
7) Daily Challenge #7 - Factorial Decomposition
8) Daily Challenge #8 - Scrabble Word Calculator
9) Daily Challenge #9 - What's Your Number?
10) Daily Challenge #10 - Calculator
11) Daily Challenge #11 - Cubic Numbers
12) Daily Challenge #12 - Next Larger Number
13) Daily Challenge #13 - Twice Linear
14) Daily Challenge #14 - Square into Squares
15) Daily Challenge #15 - Stop gninnipS My sdroW!
16) Daily Challenge #16 - Number of People on the Bus
17) Daily Challenge #17 - Double Trouble
18) Daily Challenge #18 - Triple Trouble
19) Daily Challenge #19 - Turn numbers into words
20) Daily Challenge Post #20 - Number Check
21) Daily Challenge #21 - Human Readable Time
22) Daily Challenge #22 - Simple Pig Latin
23) Daily Challenge #23 - Morse Code Decoder
24) Daily Challenge #24 - Shortest Step
25) Daily Challenge #25 - Double Cola
26) Daily Challenge #26 - Ranking Position
27) Daily Challenge #27 - Unlucky Days
28) Daily Challenge #28 - Kill the Monster!
29) Daily Challenge #29 - Xs and Os
30) Daily Challenge #30 - What is the price?
31) Daily Challenge #31 - Count IPv4 Addresses
32) Daily Challenge #32 - Hide Phone Numbers
33) Daily Challenge #33 - Did you mean...?
34) Daily Challenge #34 - WeIrD StRiNg CaSe
35) Daily Challenge #35 - Find the Outlier
36) Daily Challenge #36 - Let's go for a run!
37) Daily Challenge #37 - Name Swap
38) Daily Challenge #38 - Middle Name
39) Daily Challenge #39 - Virus
40) Daily Challenge #40 - Counting Sheep
41) Daily Challenge #41 - Greed is Good
42) Daily Challenge #42 - Caesar Cipher
43) Daily Challenge #43 - Boardgame Fight Resolver
44) Daily Challenge #44 - Mexican Wave
45) Daily Challenge #45 - Change Machine
46) Daily Challenge #46 - ???
47) Daily Challenge #47 - Alphabets
48) Daily Challenge #48 - Facebook Likes
49) Daily Challenge #49 - Dollars and Cents
50) Daily Challenge #50 - Number Neighbor
51) Daily Challenge #51 - Valid Curly Braces
52) Daily Challenge #52 - Building a Pyramid
53) Daily Challenge #53 - Faro Shuffle
54) Daily Challenge #54 - What century is it?
55) Daily Challenge #55 - Building a Pile of Cubes
56) Daily Challenge #56 - Coffee Shop
57) Daily Challenge #57 - BMI Calculator
58) Daily Challenge #58 - Smelting Iron Ingots
59) Daily Challenge #59 - Snail Sort
60) Daily Challenge #60 - Find the Missing Letter
61) Daily Challenge #61 - Evolution Rate
62) Daily Challenge #62 - Josephus Survivor
63) Daily Challenge #63- Two Sum
64) Daily Challenge #64- Drying Potatoes
65) Daily Challenge #65- A Disguised Sequence
66) Daily Challenge #66- Friend List
67) Daily Challenge #67- Phone Directory
68) Daily Challenge #68 - Grade Book
69) Daily Challenge #69 - Going to the Cinema
70) Daily Challenge #70 - Pole Vault Competition Results
71) Daily Challenge #71 - See you next Happy Year
72) Daily Challenge #72 - Matrix Shift
73) Daily Challenge #73 - ATM Heist
74) Daily Challenge #74 - Free Pizza
75) Daily Challenge #75 - Set Alarm
76) Daily Challenge #76 - Bingo! (or not...)
77) Daily Challenge #77 - Bird Mountain
78) Daily Challenge #78 - Number of Proper Fractions with Denominator d
79) Daily Challenge #79 - Connect Four
80) Daily Challenge #80 - Longest Vowel Change
81) Daily Challenge #81 - Even or Odd
82) Daily Challenge #82 - English Beggars
83) Daily Challenge #83 - Deodorant Evaporator
84) Daily Challenge #84 - Third Angle of a Triangle
85) Daily Challenge #85 - Unwanted Dollars
86) Daily Challenge #86 - Wouldn't, not Would.
87) Daily Challenge #87 - Pony Express
88) Daily Challenge #88 - Recursive Ninjas
89) Daily Challenge #89 - Extract domain name from URL
90) Daily Challenge #90 - One Step at a Time
91) Daily Challenge #91 - Bananas
92) Daily Challenge #92 - Boggle Board
93) Daily Challenge #93 - Range Extraction
94) Daily Challenge #94 - Last Digit
95) Daily Challenge #95 - CamelCase Method
96) Daily Challenge #96 - Easter Egg Crush Test
97) Daily Challenge #97 - Greed is Good
98) Daily Challenge #98 - Make a Spiral
99) Daily Challenge #99 - Balance the Scales
100) Daily Challenge #100 - Round Up
101) Daily Challenge #101 - Parentheses Generator
102) Daily Challenge #102 - Pentabonacci
103) Daily Challenge #103 - Simple Symbols
104) Daily Challenge #104 - Matrixify
105) Daily Challenge #105 - High-Sum Matrix Drop
106) Daily Challenge #106 - Average Fuel Consumption
107) Daily Challenge #107 - Escape the Mines
108) Daily Challenge #108 - Find the Counterfeit Coin
109) Daily Challenge #109 - Decorate with Wallpaper
110) Daily Challenge #110 - Love VS. Friendship
111) Daily Challenge #111 - 99 Bottles of Beer
112) Daily Challenge #112 - Functions of Integers on the Cartesian Plane
113) Daily Challenge #113 - Iterative Rotation Cipher
114) Daily Challenge #114 - Speed Control
115) Daily Challenge #115 - Look and Say Sequence
116) Daily Challenge #116 - Shortest Knight Path
117) Daily Challenge #117 - MinMinMax
118) Daily Challenge #118 - Reversing a Process
119) Daily Challenge #119 - Adding Big Numbers
120) Daily Challenge #120 - Growth of a Population
121) Daily Challenge #121 - Who has the most money?
122) Daily Challenge #122 - Clockwise Spirals
123) Daily Challenge #123 - Curry me Softly
124) Daily Challenge #124 - Middle Me
125) Daily Challenge #125 - 23 Matches or More
126) Daily Challenge #126 - The Supermarket Line
127) Daily Challenge #127 - Playing with Passphrases
128) Daily Challenge #128 - Blackjack Scorer
129) Daily Challenge #129 - Clay Pigeon Shooting
130) Daily Challenge #130 - GCD Sum
131) Daily Challenge #131 - Remove Anchor from URL
132) Daily Challenge #132 - Is my friend cheating?
133) Daily Challenge #133 - Suitcase Packing
134) Daily Challenge #134 - Rice and Chessboard Problem
135) Daily Challenge #135 - The Wide Mouthed Frog!
136) Daily Challenge #136 - The Deaf Rats of Hamelin
137) Daily Challenge #137 - Help the Bookseller

Write a function that will generate all possible combinations of grammatically correct parentheses. The function should be able to work with *n* pairs of parentheses.

Given *n = 3*, an example solution set would be:

[ "((()))", "(())()", "()(())", "()()()", "(()())" ]

Looking forward to seeing your solutions!

*Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!*

Classic DEV Post from May 23

I made it using python.

Edit: Using inbuilt function for generating permutations is a bad idea. This code works fine till n = 5 but then it takes noticeably long long time to execute. For n = 6, it took 1 minute 19 seconds!

Quick formatting tip: type

`python`

after the three backticks to get python formatting (like`'''python`

but with the correct symbol).I like how you are using the features Python gives you, even if it took a while for me to get it — after a few minutes I realized that the inner

`for`

loop was a check to see if the string`i`

is properly formatted.Thanks for this 👍 I was looking for something like this before posting but couldn't find anything.

The number of results is a Catalan number (see Catalan number on Wikipedia)

Typescript!

First, solving it with numbers. Each solution string is represented by an array of numbers with number incrementing for "(" and decrementing for ")".

For example, "(())()" is [1, 2, 1, 0, 1, 0]

The recursive helper function "solveWithNumbers" receives the beginning of a solution and returns an array with all complete solutions starting with these numbers.

The function "paren" runs "solveWithNumbers" and then converts the solution to the required format

[stackblitz.com/edit/typescript-n51vvd]

I tried using C++. Haven't tested it much. I know there exists a method in C++ to generate all permutations of a string. But this program is better optimized. It doesn't check all permutations. It stops following a sequence whenever it runs into a condition from where a valid sequence cannot be generated. For example, whenever number of closing braces are more than number of opening braces, there is no point following that recursion because it will never generate any valid permutations.

This is an

`O(n!)`

because the output is`O(n!)`

- there is no way around it. Still - it can be greatly optimized if we generate the valid combinations in order instead of generating all the combinations and filtering for the valid ones - which both increases the number of combinations we need to generate and forces us to pay for validating each configuration.First, we need to represent the combinations. It is enough to represent the positions of the opening parenthesis, as we can fill the closing parenthesis when we generate the string. So our data structure will be an

`n`

sized vector of positions. The first position is always 0, but we'll keep it in the vector anyway for the sake of simplicity.What makes a representation valid? The first position -

`p[0]`

- must be 0. Technically this means we can just use an`n-1`

sized vector, but we'll keep it in the vector anyway for the sake of simplicity.What about the other position? For each

`k`

in`[1,n)`

, what are the valid values for`p[k]`

? Obviously`p[k] > p[k-1]`

so we have a minimum. The maximum is less obvious but also easy -`k * 2`

. This is the maximum number of characters before it -`k`

opening parenthesis and`k`

closing parenthesis. There cannot be more opening parenthesis because`k`

is the`k`

th, and there cannot be more closing parenthesis because then there won't be enough opening parenthesis to match them.So, if we have

`p[0], p[1], ... p[k]`

we know the valid ranges of`p[k+1]`

- and that's enough to advance`p`

:You can see it in action at play.rust-lang.org/?version=stable...

On my machine, when built with release, it can generate all 35,357,670 combinations for

`n=16`

in between 4 and 5 seconds. Printing them takes much much much longer - even when I redirect the output to`/dev/null`

it takes half a minute, and when I don't it takes forever (didn't let it finish). I suspect other implementations will have similar problems, so you should try to time them without printing the combinations (just print how many you got)I whipped this one up in PHP, going for readability first. As I'm building the solutions from smaller solutions using recursion with a lot of duplicate requests, memoization here is a must.

Also, damn, this requires a lot of memory. At

`n=16`

it crashes when trying to claim 2GB of memory when it already has 5GB used. I'll try to see how far I can get with some optimizations, but I'm not holding my breath on this one.Yeah, here is the most memory efficient one I could think of:

It now fails with a different amount of memory allocated, but still doesn't reach 16.

With the way it grows, I'm guessing the number of strings for 16 pairs of parentheses to be around 30 million. With each string being 33 characters (16 opening + 16 closing parenthesis, + 1 null terminator) I'm looking at almost 8 GB of memory for the strings alone. No wonder my laptop can't compute it.

This is another case where dynamic programming is useful.

Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"

Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.

Hmm, that came out a bit confusing.

Hopefully the code is easier to follow...

TypeScript:

A couple of runs...