Skip to content

Instantly share code, notes, and snippets.

@sheniff
Created April 19, 2015 20:29
Show Gist options
  • Select an option

  • Save sheniff/4d08e5c2061baed2bc94 to your computer and use it in GitHub Desktop.

Select an option

Save sheniff/4d08e5c2061baed2bc94 to your computer and use it in GitHub Desktop.
Finding all possible combinations of parentheses and verify result's right using Catalan Number
function findAllCombinations(numParens) {
var totalCombs = 0;
if(numParens > 0) {
totalCombs = attachParen('', numParens, numParens, totalCombs);
}
return totalCombs;
}
function attachParen(str, open, close, total) {
if(open > 0) {
total = attachParen(str + '(', open - 1, close, total);
}
if(close > 0 && close > open) {
total = attachParen(str + ')', open, close - 1, total);
}
// show only full combinations
// we could show all the combinations just by
// changing this condition to an "else"
if(open === 0 && close === 0) {
console.log(str);
++total;
}
return total;
}
function checkNumCombinations(numParens, result) {
// Using Catalan Numbers to mathematically verify number of combinations
// http://en.wikipedia.org/wiki/Catalan_number
var expected = (function catalanNumber(numParens) {
var total = 1;
for(var i = 2; i <= numParens; i++) {
total *= (numParens + i) / i;
}
return Math.round(total);
})(numParens);
console.log('Total combinations: ' + result + '. Expected: ' + expected);
return expected === result;
}
// Testing it out
var combinations = 5;
if(checkNumCombinations(combinations, findAllCombinations(combinations))) {
console.log('OK');
} else {
console.log('Error');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment