Backtracking

I realized I ain’t learn shit in CPSC320.
Backtracking are perfect for questions like

  • Permutation
  • Combination
  • Subset

It’s easier to treat backtracking problems as a tree, and typically, answers are where leaf nodes are located. While trying to solve those problems, we are traversing the tree, and backtracking happens when we undo our last operation to path to prepare for the next iteration.

backtracking
Just remember the template to solve backtracking problems:

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
function solution() {
let ans = [];
let path = [];

/* initial call */
backtracking(...params);
return ans;

/* backtracking */
function backtracking(...params) {
// Found a leaf node
if (terminating conditions) {
ans.push(...path);
return ans;
}

// Keep traversing
for (let each node of choices) {
// Do something
backtracking(...params);
// Undo operations.
}

}
}