Skip to content

Instantly share code, notes, and snippets.

@seemaullal
Last active August 29, 2015 14:24
Show Gist options
  • Save seemaullal/c504de50ab42a57b59c1 to your computer and use it in GitHub Desktop.
Save seemaullal/c504de50ab42a57b59c1 to your computer and use it in GitHub Desktop.
Valid Parentheses Combinations

One way of solving this problem is to do so recursively: -you can always pick a left parentheses as long as you haven't used up all of your left parentheses (i.e. if the # of left parentheses is less than n)

  • you can pick a right parentheses if it does not make the combination invalid
    • it will be invalid if there are more right parentheses than left
    • if you keep track of how many left parentheses you currently have added, then you can determine whether or not you can add a right parentheses to the current combination
    • when you have added n left parentheses and n right parentheses, you have a valid result and can add it to your results set

You can use the following recursive calls to mimic this.

First you call a function getCombinations(left,right,curr) with left = n, right =0, and curr='' because you have n left parentheses to add but can't add any right yet (it would make the combination invalid since right parentheses must come after a left) and your initial result is an empty string. if (left > 0) call getCombinations(left-1, right +1, curr + '(') ) [you add a left parentheses and now must add a right parentheses to match it i.e. you add 1 to right] if (right > 0) call getCombinations(left, right-1, curr + ')' ) [you add a right parentheses] if (left = right = 0) curr is a valid combintion and you can add it to your results

Here is a visualization that shows the recursive calls for n=3

![enter image description here](https://lh3.googleusercontent.com/-LojKBSWgWG8/VaEicRGhmaI/AAAAAAAAAqo/3W4cCzGYWWY/s0/Recursion+Chart.jpg "Recursion Chart.jpg" =500) Here is a Javascript solution that incorporates these ideas:

function validParentheses(n) {
    var combos = [ ]; //to store your results
    function getCombinations(openNum,closingNum,curr) {
        if (openNum === 0 && closingNum === 0)
            combos.push(curr);
        if (openNum > 0) {
            getCombinations(openNum-1, closingNum + 1, curr + "(");
        }
        if (closingNum > 0) {
            getCombinations(openNum, closingNum - 1, curr + ")");
        }
    }
    getCombinations(n,0,"");
    return combos;

}

In the getCombinations(openNum, closingNum, curr) helper function,

  • the 1st argument is how many left parentheses you can add
  • the 2nd argument is how many right parentheses you can add.
  • since you can only add right parentheses after a left one, thes second argument is initially 0 and then gets incremented each time you add a left parentheses
  • the 3rd argument keeps track of the current result which we are adding parentheses to
  • when both the 1st and 2nd arguments are 0, you have added n pairs of parentheses and can add store the current result in the results array
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment