1. Backtracking is a child of Recursion. So there should be a Base Case

function backtrack(candidate, ...otherParameters) {
    // Check if the current candidate is a solution
    if (isSolution(candidate)) {
        processSolution(candidate);
        return;
    }
}

2. Backtracking usually involve a lot of Choices associated. Therefore, there must be a loop to go through all the choices.

• Since backtracking passes value by referenee , it mutates the original value
• Therefore once the control comes back out of the recursion, we need to revert the mutation.

function backtrack(candidate, ...otherParameters) {
    // Check if the current candidate is a solution
    if (isSolution(candidate)) {
        processSolution(candidate);
        return;
    }

		// Iterate over all possible choices for the current decision point
    const choices = generateChoices(candidate, ...otherParameters);
    for (const choice of choices) {
        // Make a choice
        makeChoice(candidate, choice);

        // Recur to the next decision point
        backtrack(candidate, ...otherParameters);

    }
}

3. Undo the choices back.

function backtrack(candidate, ...otherParameters) {
    // Check if the current candidate is a solution
    if (isSolution(candidate)) {
        processSolution(candidate);
        return;
    }

    // Iterate over all possible choices for the current decision point
    const choices = generateChoices(candidate, ...otherParameters);
    for (const choice of choices) {
        // Make a choice
        makeChoice(candidate, choice);

        // Recur to the next decision point
        backtrack(candidate, ...otherParameters);

        // Undo the choice (backtrack)
        undoChoice(candidate, choice);
    }
}

Previous

Backtracking

Next

Problems with Backtracking