Menu
This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions.
The task is to write a function Brackets(int n) that prints all combinations of well-formed brackets from 1...n. For Brackets(3) the output would be
() (()) ()() ((())) (()()) (())() ()(()) ()()() 
538
As such, the number of possible outcomes for a bracket is 2^63, or 9,223,372,036,854,775,808. That's 9.2 quintillion. In case you were wondering, one quintillion is one billion billions.
A string having brackets is said to be balanced if: A matching closing bracket occurs to the right of each corresponding opening bracket. Brackets enclosed within balanced brackets should also be balanced. It should not contain any non-bracket character.
Push an opening parenthesis on top of the stack. In case of a closing bracket, check if the stack is empty. If not, pop in a closing parenthesis if the top of the stack contains the corresponding opening parenthesis. If the parentheses are valid, then the stack will be empty once the input string finishes.
Took a crack at it.. C# also.
public void Brackets(int n) { for (int i = 1; i <= n; i++) { Brackets("", 0, 0, i); } } private void Brackets(string output, int open, int close, int pairs) { if((open==pairs)&&(close==pairs)) { Console.WriteLine(output); } else { if(open<pairs) Brackets(output + "(", open+1, close, pairs); if(close<open) Brackets(output + ")", open, close+1, pairs); } } The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..
108
Python version of the first voted answer.
def foo(output, open, close, pairs): if open == pairs and close == pairs: print output else: if open<pairs: foo(output+'(', open+1, close, pairs) if close<open: foo(output+')', open, close+1, pairs) foo('', 0, 0, 3) If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
