cassidoo-fromParens

fromParens.js

/**
  This brute forces all possible () combinations by interpreting the binary 
  representation of an increasing number with 0 as ( and 1 as ).
  Works fine for n<15. For bigger n, the amount of results will be too big for memory.
*/
function fromParens(n) {
  let ret = [],
    targetLen = n * 2, // target string length
    max = Math.pow(2, targetLen), // maximum number to look at
    current, // current number
    idx, // index iterating over current number
    left, // (current >> idx) - what is left after right-shifting current idx times
    sum, // "sum" over ( as +1 and ) as -1
    str; // current number as string
  if (!n) return ret;
  outer: for (current = 0; current < max; current++) {
    left = current;
    sum = 0;
    // check if current is a vialbe candidate
    for (idx = 0; idx < targetLen; idx++) {
      // we only have "(" left in the string -> not a candidate
      if (!left) continue outer;
      sum += left & 1 ? -1 : 1;
      // we have closed more parens than we openend -> not a candidate
      if (sum < 0) break;
      left >>= 1;
    }
    // if all opened parens were closed again
    if (sum == 0) {
      // build a string representation
      left = current;
      str = "";
      for (idx = 0; idx < targetLen; idx++) {
        str += left & 1 ? ")" : "(";
        left >>= 1;
      }
      // and push it to the results
      ret.push(str);
    }
  }
  return ret;
}

for (let i = 1; i < 12; i++) {
  console.time("i=" + i);
  console.log(fromParens(i).length, "items found");
  console.timeEnd("i=" + i);
}