Valid Parentheses Combinations

gistfile1.md

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