@blonkm/

Backtracking example

ES6

No description

fork
loading
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