Number of valid parentheses combinations

numberOfValidParenthesesCombinationsOfN.js

//inefficient O(n^2)

// Improvement Ideas
// The binary numbers must be balanced - equal number of 0s and 1s - maybe there's an efficient way to find out these numbers
// 

function getNumberOfValidParenthesesCombinationsOfN(n){
	
	var i;

	var maxValue = Math.pow(2, 2*n);

	var totalNumberOfCombinations = 0;

	for(i=0; i<maxValue; i++) {

		// console.log(i);
		var x = i;

		var bitStack = [];
		
		var debugParColletor = "";
		var debugBitColletor = "";

		// In reverse order so first LSB, last MSB 
		// 0 -> '('
		// 1 -> ')'

		// Must begin with 0 or '(' to be valid - LSB (EVEN NUMBER)
		if(x % 2 != 0) {
			bitStack.push(-1);
			// break;
		}
		else {
			for(var j=0;j<2*n;j++) {

				var bit = x % 2;
				
				if(j==0 && bit == 1){
					bitStack.push(-1);
					break;
				}

				x = Math.floor(x/2);

				if(bit == 0){
					bitStack.push(bit);
				}else{
					if(bitStack[bitStack.length-1] == 0){
						bitStack.pop(bit);
					}else{
						bitStack.push(bit);
					}
				}
				debugParColletor+=bit==0?"(":")";
				debugBitColletor+=bit;
			}
		}

		if(bitStack.length == 0){
			 // console.log(debugParColletor);
			 // console.log(debugBitColletor);
			 // console.log(i);
			// if(i%2!=0){
			// 	console.log("ODD");	
			// }
			
			totalNumberOfCombinations++;
		}

		// VERY INEFFICIENT
		// do {
			
		// } while(x > 0)

		// var paranthesisCombination = "";
		// var bnumber = "";

		// var pStack = [];
		// while (bitStack.length > 0) {

		// 	var bit = bitStack.pop();

		// 	if(bit==0)
		// 	{
		// 		pStack.push(bit);
		// 		paranthesisCombination += "(";
		// 	}
		// 	else {
		// 		if(pStack[pStack.length-1] == 0){
		// 			pStack.pop(bit);
		// 		}else{
		// 			pStack.push(bit);
		// 		}
				
		// 		paranthesisCombination += ")";
		// 	}

		// 	// if(pStack.length==0 || pStack[pStack.length-1] == bit) {
		// 	// 	pStack.push(bit);
		// 	// }else if(pStack[pStack.length-1] != bit){
		// 	// 	pStack.pop(bit);	
		// 	// }

		// 	bnumber+=bit;
		// }

		// if(pStack.length == 0){
		// 	console.log(paranthesisCombination);
		// 	console.log(bnumber);	
		// }
		
	}
	console.log(totalNumberOfCombinations)
}

//NODE JS

//node numberOfValidParenthesesCombinationsOfN.js 8

// const args = process.argv.slice(2)

// console.time('getNumberOfValidParenthesesCombinationsOfN');

// getNumberOfValidParenthesesCombinationsOfN(args[0]);

// console.timeEnd('getNumberOfValidParenthesesCombinationsOfN');

//ANY JS RUNTIME

getNumberOfValidParenthesesCombinationsOfN(8)

// 2
// ()()
// (())

// 1
// ()

// 111111
// 1+2+4+8+16+32

// 3
// ( ( () ) )
// () () ()
// (()) ()
// () (())
// ( () () )