StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h3>Overview of the problem</h3> <p>This is a classic combinatorial problem that manifests itself in many different ways. These problems are essentially identical:</p> <ul> <li>Generating all possible ways to balance <code>N</code> pairs of parentheses (i.e. this problem)</li> <li>Generating all possible ways to apply a binary operator to <code>N+1</code> factors</li> <li>Generating all full binary trees with <code>N+1</code> leaves</li> <li>Many others...</li> </ul> <h3>See also</h3> <ul> <li><a href="http://en.wikipedia.org/wiki/Catalan_number" rel="noreferrer">Wikipedia/Catalan number</a></li> <li><a href="http://www.research.att.com/~njas/sequences/A000108" rel="noreferrer">On-Line Encyclopedia of Integer Sequences/A000108</a></li> </ul> <hr> <h3>A straightforward recursive solution</h3> <p>Here's a simple recursive algorithm to solve this problem in Java:</p> <pre><code>public class Parenthesis { static void brackets(int openStock, int closeStock, String s) { if (openStock == 0 && closeStock == 0) { System.out.println(s); } if (openStock > 0) { brackets(openStock-1, closeStock+1, s + "<"); } if (closeStock > 0) { brackets(openStock, closeStock-1, s + ">"); } } public static void main(String[] args) { brackets(3, 0, ""); } } </code></pre> <p>The above prints (<a href="http://ideone.com/o0Qlt" rel="noreferrer">as seen on ideone.com</a>):</p> <pre><code><<<>>> <<><>> <<>><> <><<>> <><><> </code></pre> <p><a href="https://i.stack.imgur.com/23Ziq.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/23Ziq.jpg" alt="Recursion Tree for n=3"></a></p> <p>Essentially we keep track of how many open and close parentheses are "on stock" for us to use as we're building the string recursively.</p> <ul> <li>If there's nothing on stock, the string is fully built and you can just print it out</li> <li>If there's an open parenthesis available on stock, try and add it on. <ul> <li>Now you have <em>one less open</em> parenthesis, but <em>one more close</em> parenthesis to balance it out</li> </ul></li> <li>If there's a close parenthesis available on stock, try and add it on. <ul> <li>Now you have one less close parenthesis</li> </ul></li> </ul> <p>Note that if you swap the order of the recursion such that you try to add a close parenthesis before you try to add an open parenthesis, you simply get the same list of balanced parenthesis but in reverse order! (<a href="http://ideone.com/hWIN7" rel="noreferrer">see on ideone.com</a>).</p> <hr> <h3>An "optimized" variant</h3> <p>The above solution is very straightforward and instructive, but can be optimized further. </p> <p>The most important optimization is in the string building aspect. Although it looks like a simple string concatenation on the surface, the above solution actually has a "hidden" <code>O(N^2)</code> string building component (because concatenating one character to an immutable <code>String</code> of length <code>N</code> is an <code>O(N)</code> operation). Generally we optimize this by using a mutable <code>StringBuilder</code> instead, but for this particular case we can also simply use a fixed-size <code>char[]</code> and an <code>index</code> variable.</p> <p>We can also optimize by simplifying the recursion tree. Instead of recursing "both ways" as in the original solution, we can just recurse "one way", and do the "other way" iteratively.</p> <p>In the following, we've done both optimizations, using <code>char[]</code> and <code>index</code> instead of <code>String</code>, and recursing only to add open parentheses, adding close parentheses iteratively: <a href="http://ideone.com/esrdq" rel="noreferrer">(see also on ideone.com)</a></p> <pre><code>public class Parenthesis2 { public static void main(String[] args) { brackets(4); } static void brackets(final int N) { brackets(N, 0, 0, new char[N * 2]); } static void brackets(int openStock, int closeStock, int index, char[] arr) { while (closeStock >= 0) { if (openStock > 0) { arr[index] = '<'; brackets(openStock-1, closeStock+1, index+1, arr); } if (closeStock-- > 0) { arr[index++] = '>'; if (index == arr.length) { System.out.println(arr); } } } } } </code></pre> <p>The recursion logic is less obvious now, but the two optimization techniques are instructive.</p> <hr> <h3>Related questions</h3> <ul> <li><a href="https://stackoverflow.com/questions/1380610/checking-string-has-balanced-parentheses">Checking string has balanced parentheses</a></li> <li><a href="https://stackoverflow.com/questions/2711032/basic-recursion-check-balanced-parenthesis">Basic Recursion, Check Balanced Parenthesis</a></li> <li><a href="https://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-giv">The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?</a></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload