Backtracking

Common Algorithm

General Form: Roll-back

void backtrack(vector<int> &arr, vector<int> &num, vector<bool> &visited, vector<vector<int>> &ans) {
    // 1. Termination case
    if (arr.size() == num.size()) {
        ans.push_back(arr);
        return;
    }

    // 2. Try every possible cases
    for (int i=0; i<num.size(); i++) {
        // 3. Check if solution is viable
        if (visited[i]) continue;

        // 4. Move to next state
        arr.push_back(num[i]);
        visited[i] = true;

        // 5. Recursively check next state
        backtrack(arr, num, visited, ans);

        // 6. Roll back to previous state
        arr.pop_back();
        visited[i] = false;
    }   
}

General Form II: Swapping

void backtrack(int start, vector<int> &num, vector<vector<int> > &res) {
    if (start >= num.size()) res.push_back(num);
    for (int i = start; i < num.size(); ++i) {
        swap(num[start], num[i]);
        backtrack(start + 1, num, res);
        swap(num[start], num[i]);
    }
}

Allow duplicate elements and doesn't allow duplicate elements

Recursion

Base Case: Any recursive method must have a terminating condition. Terminating condition is one for which the answer is already known and we just need to return that.

Number of Recursive calls: There is an upper limit to the number of recursive calls that can be made. To prevent this make sure that your base case is reached before stack size limit exceeds.

So, if we want to solve a problem using recursion, then we need to make sure that:

  • The problem can broken down into smaller problems of same type.
  • Problem has some base case(s).
  • Base case is reached before the stack size limit exceeds.

Backtracking

Backtracking is a technique used to build up to a solution to a problem incrementally. These "partial solutions" can be phrased in terms of a sequence of decisions. Once it is determined that a "partial solution" is not viable (i.e. no subsequent decision can convert it into a solution) then the backtracking algorithm retraces its step to the last viable "partial solution" and tries again.

Visualizing the decisions as a tree, backtracking has many of the same properties of depth-first search. The difference is that depth-first search will guarantee that it visits every node until it finds a solution, whereas backtracking doesn't visit branches that are not viable.

Because backtracking breaks problems into smaller subproblems, it is often combined with dynamic programming, or a divide-and-conquer approach.

Important Concepts

  • State: A "partial solution" to the problem.
  • Rejection: A condition that rejects a partial solution as "unrecoverable". Without rejection criteria, backtracking is the same as depth-first search.
  • Viable: A state that may still lead to a solution. All states that fail the rejection criteria are not viable.
  • Heuristic: Backtracking will (eventually) look at all the different viable nodes by recursively applying all the possible decisions.
  • Termination: The concept of determining that there are no nodes / states along a particular branch, so it is not worth visiting those nodes.

A backtracking algorithm is conceptually very similar to depth-first search (DFS). A DFS will "roll back" the current state to a node up the tree once it reaches a leaf node, and is guaranteed to find a solution (or search every node). Backtracking can be thought of as DFS with early pruning.

Recursion

Backtracking is often implemented using recursion, so it helps to be familiar with how to write recursive functions.

Stacks

If you need a lot of nested recursive calls, trying to use simple recursion might result in a stack overflow error. You can mimic recursion by using a stack data structure.

Generalized Algorithm

A recursive implementation of a backtracking algorithm takes the general form

function doBacktrack( current ):
    if current is a solution:
        return current
    for each decision d from current:
        new_state <- state obtained from current by making decision d
        if new_state is viable:
            sol <- doBacktrack(new_state)
            if sol is not None:
                return sol
    # indicate there is no solution
    return None

results matching ""

    No results matching ""