Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14function solve(state, results) {
  if (/* the state is a complete answer */) {
    results.push([...state]);        // COPY, or every result aliases the same array
    return;
  }

  for (const choice of availableChoices(state)) {
    if (!isValid(choice, state)) continue;   // pruning

    state.push(choice);              // choose
    solve(state, results);           // explore
    state.pop();                     // un-choose
  }
}

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// Style 1: at each index, decide to include it or not. A binary tree of depth n.
function subsetsInclude(nums) {
  const results = [];

  function walk(index, current) {
    if (index === nums.length) {
      results.push([...current]);          // a complete decision set
      return;
    }
    // Choice A: skip nums[index].
    walk(index + 1, current);

    // Choice B: take it.
    current.push(nums[index]);
    walk(index + 1, current);
    current.pop();                          // undo
  }

  walk(0, []);
  return results;
}

// Style 2: build from a start index. Every node in the tree is itself an answer.
function subsetsStart(nums) {
  const results = [];

  function walk(start, current) {
    results.push([...current]);              // record at every node, not just leaves
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      walk(i + 1, current);                 // i + 1: never reuse an element
      current.pop();
    }
  }

  walk(0, []);
  return results;
}

console.log('include/exclude:', subsetsInclude([1, 2, 3]));
console.log('start index:    ', subsetsStart([1, 2, 3]));
console.log('count for n=3:', subsetsStart([1, 2, 3]).length, '= 2^3');
console.log('empty input:', subsetsStart([]));

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
31function broken(nums) {
  const results = [];
  function walk(start, current) {
    results.push(current);                  // NO COPY — pushing the live array
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      walk(i + 1, current);
      current.pop();
    }
  }
  walk(0, []);
  return results;
}

console.log('without copying:', broken([1, 2]));
console.log('every entry is the same array, now empty after unwinding');

function fixed(nums) {
  const results = [];
  function walk(start, current) {
    results.push([...current]);              // snapshot
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      walk(i + 1, current);
      current.pop();
    }
  }
  walk(0, []);
  return results;
}
console.log('with copying:   ', fixed([1, 2]));

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
27function permutations(nums) {
  const results = [];
  const used = new Array(nums.length).fill(false);

  function walk(current) {
    if (current.length === nums.length) {
      results.push([...current]);
      return;
    }
    // Start from 0 every time: order matters, so any unused element can come next.
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(nums[i]);
      walk(current);
      current.pop();
      used[i] = false;                       // undo BOTH pieces of state
    }
  }

  walk([]);
  return results;
}

console.log(permutations([1, 2, 3]));
console.log('count for n=3:', permutations([1, 2, 3]).length, '= 3!');
console.log('count for n=4:', permutations([1, 2, 3, 4]).length, '= 4!');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function combinations(n, k) {
  const results = [];

  function walk(start, current) {
    if (current.length === k) { results.push([...current]); return; }

    // Pruning: stop if not enough numbers remain to reach length k.
    const needed = k - current.length;
    for (let i = start; i <= n - needed + 1; i++) {
      current.push(i);
      walk(i + 1, current);
      current.pop();
    }
  }

  walk(1, []);
  return results;
}

console.log('choose 2 from 4:', combinations(4, 2));
console.log('choose 3 from 4:', combinations(4, 3));
console.log('count:', combinations(5, 3).length, '= 5 choose 3 = 10');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function combinationSum(candidates, target) {
  const results = [];

  function walk(start, current, remaining) {
    if (remaining === 0) { results.push([...current]); return; }
    if (remaining < 0) return;                 // overshot: prune

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      walk(i, current, remaining - candidates[i]);   // i, not i+1: reuse allowed
      current.pop();
    }
  }

  walk(0, [], target);
  return results;
}

console.log(combinationSum([2, 3, 6, 7], 7));      // [[2,2,3],[7]]
console.log(combinationSum([2, 3, 5], 8));         // [[2,2,2,2],[2,3,3],[3,5]]
console.log(combinationSum([2], 1));               // []

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
32function subsetsWithDup(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const results = [];

  function walk(start, current) {
    results.push([...current]);
    for (let i = start; i < sorted.length; i++) {
      // i > start means this is not the first choice at this level, so a repeat
      // here would produce a subset we have already generated.
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      current.push(sorted[i]);
      walk(i + 1, current);
      current.pop();
    }
  }

  walk(0, []);
  return results;
}

console.log('with the skip:', subsetsWithDup([1, 2, 2]));

// Without the skip, you get [2] twice and [1,2] twice.
function withoutSkip(nums) {
  const s = [...nums].sort((a, b) => a - b), out = [];
  (function walk(start, cur) {
    out.push([...cur]);
    for (let i = start; i < s.length; i++) { cur.push(s[i]); walk(i + 1, cur); cur.pop(); }
  })(0, []);
  return out;
}
console.log('without it:   ', withoutSkip([1, 2, 2]), '← duplicates');

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
27function combinationSumCounted(candidates, target, prune) {
  const results = [];
  let calls = 0;

  function walk(start, current, remaining) {
    calls++;
    if (remaining === 0) { results.push([...current]); return; }
    // This check is needed for termination, so both versions keep it.
    if (remaining < 0) return;

    for (let i = start; i < candidates.length; i++) {
      // The prune being measured: on sorted input, once a candidate is too big
      // every later one is too, so abandon the whole rest of the loop.
      if (prune && candidates[i] > remaining) break;
      current.push(candidates[i]);
      walk(i, current, remaining - candidates[i]);
      current.pop();
    }
  }

  walk(0, [], target);
  return { found: results.length, calls };
}

const sortedCandidates = [2, 3, 5, 7, 11];
console.log('no pruning:  ', combinationSumCounted(sortedCandidates, 20, false));
console.log('with pruning:', combinationSumCounted(sortedCandidates, 20, true));

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
30function solveNQueens(n) {
  const solutions = [];
  const queens = [];                    // queens[row] = column

  // Instead of scanning the board, track which columns and diagonals are taken.
  const cols = new Set();
  const diag = new Set();               // row - col is constant along one diagonal
  const anti = new Set();               // row + col is constant along the other

  function place(row) {
    if (row === n) {
      solutions.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;

      queens.push(col); cols.add(col); diag.add(row - col); anti.add(row + col);
      place(row + 1);
      queens.pop(); cols.delete(col); diag.delete(row - col); anti.delete(row + col);
    }
  }

  place(0);
  return solutions;
}

console.log('4-queens has', solveNQueens(4).length, 'solutions:');
solveNQueens(4).forEach((board, i) => { console.log(` solution ${i + 1}:`); board.forEach(r => console.log('   ' + r)); });
console.log('8-queens has', solveNQueens(8).length, 'solutions');

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
28function exist(board, word) {
  const rows = board.length, cols = board[0].length;

  function search(r, c, index) {
    if (index === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[index]) return false;

    const saved = board[r][c];
    board[r][c] = '#';                  // mark as used on the current path

    const found = search(r + 1, c, index + 1) || search(r - 1, c, index + 1) ||
                  search(r, c + 1, index + 1) || search(r, c - 1, index + 1);

    board[r][c] = saved;                // restore for other paths
    return found;
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (search(r, c, 0)) return true;
  return false;
}

const board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']];
console.log('ABCCED:', exist(board, 'ABCCED'));   // true
console.log('SEE:   ', exist(board, 'SEE'));      // true
console.log('ABCB:  ', exist(board, 'ABCB'));     // false, cannot reuse a cell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function partitionPalindromes(s) {
  const results = [];
  const isPal = (str, lo, hi) => {
    while (lo < hi) { if (str[lo] !== str[hi]) return false; lo++; hi--; }
    return true;
  };

  function walk(start, current) {
    if (start === s.length) { results.push([...current]); return; }

    for (let end = start; end < s.length; end++) {
      if (!isPal(s, start, end)) continue;         // prune: not a valid piece
      current.push(s.slice(start, end + 1));
      walk(end + 1, current);
      current.pop();
    }
  }

  walk(0, []);
  return results;
}

console.log(partitionPalindromes('aab'));
console.log(partitionPalindromes('a'));
console.log(partitionPalindromes('aba'));

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// Count the ways to climb n stairs taking 1 or 2 steps. Backtracking explores
// every path; but we only need the COUNT, and paths share subproblems.
let backtrackCalls = 0;
function countWaysBacktrack(n) {
  backtrackCalls++;
  if (n === 0) return 1;
  if (n < 0) return 0;
  return countWaysBacktrack(n - 1) + countWaysBacktrack(n - 2);
}

let memoCalls = 0;
function countWaysMemo(n, memo = new Map()) {
  memoCalls++;
  if (n === 0) return 1;
  if (n < 0) return 0;
  if (memo.has(n)) return memo.get(n);
  const result = countWaysMemo(n - 1, memo) + countWaysMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

for (const n of [10, 20, 30]) {
  backtrackCalls = 0; memoCalls = 0;
  const a = countWaysBacktrack(n), b = countWaysMemo(n);
  console.log(`n=${n}: answer ${a} | backtracking ${backtrackCalls.toLocaleString('en-US')} calls | memoised ${memoCalls} calls`);
}
console.log('If you need a COUNT or a BEST, not a LIST, you probably want DP.');