@blonkm/

# Backtracking example

## No description

main.js
```1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
```
```/* backtracking
*
* example: find all sets of three increasing numbers a,b,c that sum to x
*
* backtracking is nothing but recursion with added constraints
* e.g. the constraint that a<b and b<calls
* the more constraints can be found the faster the
* backtracking will be done
*
* because each solution is visited multiple times
* (taken from stack), we need to either filter duplicates
* after coming back from the stack, or we need to
* check for duplicates as we go and add to a list
* of solutions (which I've done here)
*/

const sum2x = function(x, a,b,c){
if (a>x || b>x || c>x || a+b>x || b+c>x || a+c>x || a+b+c>x)
return false;
if (a>b || b>c)
return false;
// calls++;
if (a+b+c == x && a<b && b<c) {
solutions[[a,b,c].join()] = 1;
return true;
}
else {
if (sum2x(x, a+1, b  , c  ) == x)
return true;
if (sum2x(x, a  , b+1, c  ) == x)
return true;
if (sum2x(x, a  , b  , c+1) == x)
return true;
}
return false;
}

let solutions;

for (let i of [20]) {
solutions = [];
sum2x(i, 0,0,0);
console.log(i, Object.keys(solutions));
}```
Babel Compiler v6.4.4 Copyright (c) 2014-2015 Sebastian McKenzie