Programming Problem 5: Sum to 100

problem5.js

// Problem 5
// Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
// http://www.shiftedup.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9],
  symbols = ['+', '-', ' '],
  perms = [];

function kLengthPermutations(permArr, k, prefix) {

  if (k === 0) {
    perms.push(prefix);
    return;
  }

  for (var i = 0; i < permArr.length; i++) {
    newPrefix = (prefix ? prefix : "") + permArr[i]; 
    kLengthPermutations(permArr, k - 1, newPrefix);
  }
}

function intertwineArrays(arr1, arr2) {
  var output = [];
  var shorterLength = arr1.length < arr2.length ? arr1.length : arr2.length;

  for (var i = 0; i < shorterLength; i++) {
    output.push(arr1[i]);
    output.push(arr2[i]);
  }

  if (arr1.length > arr2.length) output.push(arr1[i]);

  return output;
}


kLengthPermutations(symbols, 8);

for (var i = 0; i < perms.length; i++) {
  var combinedArray = intertwineArrays(nums, perms[i]);
  var sumString = combinedArray.join('').replace(/\s+/g, '');
  if (eval(sumString) === 100) console.log(sumString);
}