Some Questions About Backtracking and DFS Algorithms

This article uses the simplest examples to address several common questions readers have about backtracking and DFS algorithms:

1. What is the difference between backtracking and DFS algorithms?

2. The Core Framework of Backtracking Algorithms mentions that the backtracking template involves making choices before recursion and undoing them afterward. Why do we sometimes see code that "makes choices" before a for loop and "undoes choices" after it?

3. Can the backtrack/dfs/traverse function have return values?

4. Is it better to write the base case and pruning before the recursive calls or at the beginning of the function?

What is the Difference Between Backtracking and DFS Algorithms?

Readers often ask why there are articles on backtracking algorithms on the site but not on DFS algorithms.

Some readers also question the backtracking template mentioned in the Core Framework of Backtracking Algorithms, which involves making choices before recursion and undoing them afterward, like this:

void backtrack(...) {
    if (reached the leaf node) {
        // reached the leaf node, stop recursion
        return;
    }

    for (int i = 0; i < n; i++) {
        // make a choice
        ...

        backtrack(...)

        // undo the choice
        ...
    }
}

But why do you sometimes see code "making choices" before the for loop and "undoing choices" after the for loop:

void backtrack(...) {
    if (reached the leaf node) {
        // reached the leaf node, stop recursion
        return;
    }
    // make a choice
    ...

    for (int i = 0, i < n; i++) {
        backtrack(...)
    }

    // undo the choice
    ...
}