Backtracking Algorithms

Backtracking Algorithms are a strategy usually used to explore permutations or combinations of a certain size.

It allows the algorithm to explore a certain combination/solution and then to undo the choice to explore other possibilities.

Below is pseudo code for a Backtracking Algorithm:

def backtrack(state):
    if is_solution(state):
        process(state)
        return

    for choice in valid_choices(state):
        make_choice(state, choice)
        backtrack(state)
        undo_choice(state, choice)

Generate Binary

Generate Binary is a simple example of a Backtracking Algorithm.

def generate_binary(n, prefix=""):
    if n == 0:
        print(prefix)
        return

    generate_binary(n - 1, prefix + "0")
    generate_binary(n - 1, prefix + "1")

generate_binary(2)

>>>

00
01
10
11

In this function, we have our check for is_solution being if n == 0, we print out the current prefix.

This is due to the fact that we are generating all binary strings of lenght n where each position can either be 0 or 1.

In Generate Binary, there is only two choices 0 or 1 but n determines how long the string will be.

By recursively calling the function with n-1 and concatenating a new prefix, we end up exploring all permutations of size n.

The runtmime of this algorithm is: O(2^n) because at each level there is a binary choice 0 or 1, and this choice is made to the power of n times (the depth of the tree).

Heaps Algorithm

Not to be confused with the Heap Datastructure or Heapsort Algorithm.

Heaps Algorithm finds all permutations of an array of size n.

def heapPermutation(a, size):
    if size == 1:
        print(a)
        return

    for i in range(size):
        heapPermutation(a, size - 1)

        if size & 1:
            a[0], a[size - 1] = a[size - 1], a[0]
        else:
            a[i], a[size - 1] = a[size - 1], a[i]


a = [1, 2, 3]
n = len(a)
heapPermutation(a, n)

>>>

[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]

Heaps Algorithm uses a swap rule that depends on whether the size is even or odd. It recursively explores all permutations by moving elements into the final position using This ensures every element appears in each position exactly once.

The size variable that is reduced on each subsequent call acts as a sliding window to explore all permutations.

The runtime of this algorithm is: O(n * n!)

The reason its n is because need to loop on each recursive call over n and n! since this is exploring every permutation.

Iterative Heaps Algorithm

Heaps Algorithm can also be implemented using an iterative approach.

The core changes required for an interative approach are:

• i - This variable acts as tracking the recursion depth

• control - A vector that tracks the number of explorations at each level.

• result - The generated permutations

• The main purpose of the loop is to cover all possible permutations with i < size

• control[i] < i determins if we have exhausted all permutations at the current level

• When we find a permutation at a certain level, we reset i to 0, which is the root this is key for performing a DFS search

• Once we exhaust all permutations at a certain level, we increment i to go to the next level

fn heaps_algo_iter(input: &mut PasswordInput) -> Vec<String> {
    let size = input.searchspace.len();

    // In terms of recursion, i acts as the depth. This algorithm is DFS.
    let mut i = 0;

    // Control, tracks the number of permutations at each level or in terms of recursion,
    // the branches.
    let mut control = vec![0; size];
    let mut result = vec![input.searchspace.iter().collect()];

    // While current level iteration is less than size, in the recursive algorithm
    // the depth of the recursion is equal to the size.
    while i < size {

        // If control shows less than i, we still need to do more exploration at this depth.
        if control[i] < i {
            println!("control[i]: {:?}", &control[i]);
            println!("i: {:?}", i);

            let idx = match i & 1 {
                1 => 0,
                _ => 1
            };

            input.searchspace.swap(idx, i);
            result.push(input.searchspace.iter().collect());

            // Increase the amount of items found at this iteration.
            control[i] += 1;
            i = 0; // go back to the root
        } else {
            // The exploration of permutations at this level is exhausted, reset control
            // at this iteration and increment i.
            control[i] = 0;
            i += 1; // backtrack
        }

    }

    result

}

Did you find this page helpful? Consider sharing it 🙌