8.9 Parens

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.
EXAMPLE
Input: 3
Output: ((())), (()()), (())(), ()(()), ()()()

To be honest, I've spent some time trying to find a right algorithm here. Initially I assumed there must be a way to get from printParens(n) to printParens(n+1) by adding () in some places (my idea was: from middle until the end for each element of printParens(n)). I couldn't make it work without duplicates 🤷‍♀️, so I started searching for a different algorithm.

I decided to look into the rules that make adding a new paren valid or invalid. For instance, when we look at ()() - how do we figure out that the last paren has to be ) - as we can clearly see that ()() is valid and ()(( is not ?

First of all, the number of right parens and left parens has to match (and be equal to our argument n). Secondly, the number of left parens (() at any index has to always be bigger or equal than the number of right parens - we can't close a paren before opening it. And that is actually it! 🙌 On the next step I tried to build recursion out of this logic.

I've created a helper function getParens, which would take 2 arguments: left and right, which would stand for the number of left and right parens that we can use. Let's say we want to get all pairs of parent for n = 3 - that would mean that we start with left = 3 and right = 3. With every step we would subtract 1 either from first or from second argument - depending on what type of paren - left or right - we're adding.

Note that for recursion we will be going backwards - so, we would need to invert the logical rules described above . So, to get from the string ()( to ()() (but not to ()(() we need to take into account that a left paren (() can be added to existing string ()( only if there was a matching right paren already added to the string at the previous recursion steps. Or, in other words, if the number of right parens that are still in store is smaller than the number of left parens - as we know that we're always starting with an equal number.

On each step of the recursion we can add either ) or ( to each of the combinations that we had on the previous step. Using the rule from above, we can add ( only in case left > right - otherwise we would add an opening paren before we have any closing ones. And we can always add ')' to the existing combination - unless we've run out of parens to use.

If both left and right parens in store are on 0, that means that we've found our valid combination and can start adding brackets to the empty string. Otherwise, if number of left or right brackets goes to below 0, we just want to return an empty array (so that we would map over nothing on the next steps).

And this is how it looks in JS:

function printParens(number) {
  function getParens(left, right){
    if (left < 0 || right < 0) { return []; }
    if (left === 0 && right === 0) { return ['']; }

    const withRight = getParens(left, right-1).map(elem => elem + ')');

    if (left > right) { 
      const withLeft = getParens(left-1, right).map(elem => elem + '(');
      return [...withRight, ...withLeft]
    } 
    return withRight;
  }
  return getParens(number, number)
}