Gragh - 1 year ago 59
Javascript Question

# Why does this recursive function skip numbers?

I'm trying to find the various possibilities to equal 100 with digits 1-9. This function produces the desired results, but also others which I had not intended. The other results add up to 100, but without some of these digits, like leaving out 3 or 6. Why are these other results included?

``````    var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var signs = ["+", "-", "N"];
var results = [];
find100("1");
function find100(expr) {
if (eval(expr.replace(/N/g, "")) === 100) {
results.push(expr);
} else {
for (var i = eval(expr.substring(expr.length - 1, expr.length)) + 1; i <=
nums.length; i++) {
signs.forEach(function(sign) {
var expr2 = expr;
find100(expr2 += sign + i);
});
}
}
}
``````

Desired output:

``````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+45-67+8-9,
123-4-5-6-7+8-9,
123-45-67+89
``````

It's adding undesired results because your first loop iterates through each of the remaining numbers and adds ANY results that evaluate to 100, even if it has skipped a number to do so. If the method finds a solution for a number it adds the solution to `results` - which is correct, however if it doesn't find a solution it moves onto the next number anyway. This is the source of the skipped numbers. If there was no solution for a number it should have not continued to the next number.

As to how to fix it, that's a different question (but why not ...)

The difference here is that you can ONLY get a result if for any number there exists an expression that uses all remaining numbers.

``````var results = [];
var operations = [ "+", "-", "" ];
var expected = 100;
var limit = 10;

function findExpression(expr, next) {
if (next === limit) {
eval(expr) === expected && results.push(expr);
} else {
operations.forEach(function(operation) {
findExpression(expr + operation + next, next + 1);
});
}
}

``````<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.0/jquery.min.js"></script>