find all combinations in '123456789' that lead to 100 with +/- opts (hint: DFS)

dfs.js

// https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
// Answer to prob#5
function dfs(currentPath, currentValue, str) {
  var strLen = str.length;
  if (strLen < 2) {

    if (strLen === 0 || str === '') {
      if (currentValue === 100) console.log(currentPath);
    } else {
      var lastValue = parseInt(str, 10);
      if (currentValue + lastValue === 100) {
        console.log(currentPath + ' + ' + str);
      } else if (currentValue - lastValue === 100) {
        console.log(currentPath + ' - ' + str);
      }
    }
    return;
  }

  for (var i = 1; i <= strLen; i++) {
    var valueStr = str.substring(0, i);
    var value = parseInt(valueStr, 10);
    var remainingStr = str.substring(i, strLen);

    
    if (currentPath === '') {
      dfs(valueStr, currentValue + value, remainingStr);
      continue;
    }
    dfs(currentPath + ' + ' + valueStr, currentValue + value, remainingStr);
    dfs(currentPath + ' - ' + valueStr, currentValue - value, remainingStr);
  }
}

dfs('', 0, '123456789');

Solutions (11)

1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 - 4 - 5 - 6 - 7 + 8 - 9
123 + 45 - 67 + 8 - 9
123 - 45 - 67 + 89