splitCost.js

const _ = require('lodash');
const getCombination = arr => i => arr.filter((v,j) => i & Math.pow(2, j));
const solve = (a, b) => {
  const unders = a.length > b.length ? b : a;
  const ups = a.length > b.length ? a : b;
  if (!unders.length || !ups.length) return 0;
  const m = Math.pow(2, unders.length);
  const n = Math.pow(2, ups.length);
  const getUndersCombination = getCombination(unders);
  const getUpsCombination = getCombination(ups);
  const underSumMap = {};
  for (var i = 0; i < m; i++) {
    const targetSum = _.sum(getUndersCombination(i));
    if (!underSumMap[targetSum]) underSumMap[targetSum] = i;
  }
  let undersIndex, upsIndex;
  for (var j = 1; j < n - 1; j++) {
    const targetSum = _.sum(getUpsCombination(j));
    undersIndex = underSumMap[targetSum];
    upsIndex = j;
    if (undersIndex) break;
  }
  if (!undersIndex) return unders.length + ups.length - 1;
  return solve(getUndersCombination(undersIndex), getUpsCombination(upsIndex))
          +
         solve(getUndersCombination(m - 1 - undersIndex), getUpsCombination(n - 1 - upsIndex));
}