题解 | #五八文字碰碰消#

// 参考：********的22-括号生成 
// 思路：使用回溯记录数量，五看成左括号，八看成右括号
// 不符合的条件的直接剪枝 

/**
 * 输入整数n，返回可消除为空字符串的的n组"五八"字符串数量。
 * @param n int整型 
 * @return int整型
 */
function getTargetNumber(n) {
  let res = 0;
  backtracing(n, n);
  return res;

  function backtracing(fi, ei) {
    if (fi == 0 && ei == 0) {
      res++;
      return;
    }
    if (fi > 0) {
      backtracing(fi - 1, ei);
    }
    // 保证八比五少
    if (ei > fi) {
      backtracing(fi, ei - 1);
    }
  }
}

module.exports = {
  getTargetNumber: getTargetNumber,
};