# Algorithm for placing plus and minus signs between digits so that the result is 100

December 7, 2013 Leave a comment

Yesterday I found the following programming problem:

*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 100.*

This problem has 11 solutions and they are demonstrated here: Fun with numbers: place plus/minus signs between the digits.

1 + 2 + 34 – 5 + 67 – 8 + 9 = 100

12 + 3 – 4 + 5 + 67 + 8 + 9 = 100

123 – 4 – 5 – 6 – 7 + 8 – 9 = 100

123 + 4 – 5 + 67 – 89 = 100

123 + 45 – 67 + 8 – 9 = 100

123 – 45 – 67 + 89 = 100

12 – 3 – 4 + 5 – 6 + 7 + 89 = 100

12 + 3 + 4 + 5 – 6 – 7 + 89 = 100

1 + 23 – 4 + 5 + 6 + 78 – 9 = 100

1 + 23 – 4 + 56 + 7 + 8 + 9 = 100

1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100

But the page in the link provides only answers without an algorithm, that’s why I decided to write it myself.

At first let’s simplify the problem and use only ‘+’ and ‘-‘ operations, without concatenation of numbers. Then we will have some kind of a tree with 2 branches for each node, the left branch is ‘+’ operation, the right branch is ‘-‘ operation. For numbers [1 2 3 4] and sum=6 the tree will look like this:

Then we should modify the algorithm so that besides ‘+’ and ‘-‘ we can put ‘nothing’ between numbers. We will have the tree above, but with 3 child nodes for each node instead of 2. Also the ‘nothing’ operator will build slightly different nodes. Here is their comparison:

- ‘+’ operator: [1 2 3 4] sum 100 -> [2 3 4] sum 99
- ‘-‘ operator: [1 2 3 4] sum 100 -> [-2 3 4] sum 99
- ‘nothing’ operator: [1 2 3 4] sum 100 -> [12 3 4] sum 100

For the ‘+’ operator we call “findPaths(99, 2, index+1)”, for nothing operator we will call “findPaths(100, 12, index+1)”. Here is the updated algorithm:

var digits = [1,2,3,4,5,6,7,8,9]; var searchSum = 100; function concatPrefix(prefix, paths) { return paths .filter(function(p) { return p.length > 0; }) .map(function(p) { return prefix.concat(p); }); } function findPaths(sum, previousNumber, index) { var previousDigit = Math.abs(previousNumber%10); if (index >= digits.length) { return sum == previousNumber ? [[previousDigit]] : []; } var currentDigit = digits[index]; var concatenatedNumber = previousNumber >= 0 ? 10*previousNumber + currentDigit : 10*previousNumber - currentDigit; var plusPaths = findPaths(sum-previousNumber, currentDigit, index+1); var minusPaths = findPaths(sum-previousNumber, -currentDigit, index+1); var concatPaths = findPaths(sum, concatenatedNumber, index+1); var paths = []; Array.prototype.push.apply(paths, concatPrefix([previousDigit, '+'], plusPaths)); Array.prototype.push.apply(paths, concatPrefix([previousDigit, '-'], minusPaths)); Array.prototype.push.apply(paths, concatPrefix([previousDigit, '&'], concatPaths)); return paths; } var foundPaths = findPaths(searchSum, digits[0], 1); if (foundPaths.length == 0) { console.log("no paths were found"); } else { for (var i = 0; i < foundPaths.length; i++) { console.log(foundPaths[i].join("").replace(/&/g, "")); } }

Also there is another algorithm: to generate an array with all possible combinations, then parse each row and check its sum.

It is quite slower, but it is more generic and can work for other operations:

var numbers = [1,2,3,4,5,6,7,8,9]; var sum = 100; var signs = ['+', '-', '&']; var numbersInnerLength = numbers.length-1; var cLength = Math.pow(signs.length, numbersInnerLength); var combinations = []; for (var i = 0; i < cLength; i++) { var newArray = []; for (var j = 0; j < numbers.length; j++) { newArray[j*2] = numbers[j]; } combinations.push(newArray); } for (var k = 0; k < numbersInnerLength; k++) { var periodLength = cLength / Math.pow(signs.length, k+1); var signIndex = 0; for (var i = 0; i < cLength; i+=periodLength) { for (var j = 0; j < periodLength && i+j < cLength; j++) { combinations[i+j][k*2+1] = signs[signIndex]; } signIndex = (signIndex+1)%signs.length; } } for (var i = 0; i < combinations.length; i++) { var combination = combinations[i]; var cstr = combination.join("").replace(/&/g, ""); if (eval(cstr) == sum) { console.log(cstr); } }

Recursion algorithm example on jsFiddle: http://jsfiddle.net/2CxQC/

Eval algorithm example: http://jsfiddle.net/ek3p2/

This algorithm has a high complexity and requires 3^8 (=6561) comparisons. But I can’t find a better algorithm so checking all combinations seems to be the best way to solve it.