What is Backtracking?

Before moving towards Backtracking, let's understand a more basic approach to problem-solving: Exhaustive Search!

What is Exhaustive Search?

→ Exhaustive Search is an algorithmic technique in which first all possible solutions are listed out and then we select the most feasible solution. Since it follows the most naive approach, it is a.k.a Brute-Force Search.

This approach is one of the most expensive algorithmic techniques, mainly in terms of time complexity. It is also, therefore, one of the most naive ones. The steps to generate solution via this method are pretty simple.

solve(parameters)
{
    generate all possible solutions
    ans = select most feasible solution
    return ans
}

Example: Given an array, generate all possible subsequences from the array.

void printAllPermutations(string str, int left, int right)
{
    if ( left == right )
        print(str)
    
    for( i = l to r+1 )
    {
        //swap
        swap(str[left], str[i])
        permute(str, left+1, right)
        //undo
        swap(str[left], str[i])
    }
}

Backtracking

Backtracking is an algorithmic paradigm aimed at improving the time complexity of the exhaustive search technique if possible. Backtracking does not generate all possible solutions first and checks later. It tries to generate a solution and as soon as even one constraint fails, the solution is rejected and the next solution is tried.

A backtracking algorithm tries to construct a solution incrementally, one small piece at a time. It's a systematic way of trying out different sequences of decisions until we find one that works.

Let us try to understand this technique by an example.

→ One of the most common problems solved by backtracking is to find the correct path in a maze from start point to destination.

How do we normally solve this problem?

• We select one way and try to move forward towards the destination.
• What if we reach a point where we can’t move towards the destination?
• We backtrack on our path and try to explore other paths.

This is the main idea of Backtracking! A backtracking algorithm may look something like this →

solve(parameters)
{
    if ( solution works )
        return solution
    else
    {
        // Backtrack, discard current solution
        return solve(modified_parameters) // generate next solution
    }
}

Most constraint-satisfaction or optimization problems can be solved by alternate algorithmic techniques such as Dynamic Programming or Greedy Technique but sometimes Backtracking is the only way to solve the problem, suggesting that you need to explore and check all possible solutions to reach the correct solution.

Example: Given an integer array arr consisting of positive integers, print all the subsets of elements that add up to given number target_sum.

We are given an array of distinct values and we need to generate all possible subsets that can be generated:

void subsetSum(int[] arr, int target_sum, int[] curr_subset, int curr_sum, int curr_index)
{
    if ( curr_index == arr.length )
    {
        if ( curr_sum == target_sum )
        {
            for ( i = 0 to curr_subset.length - 1 )
                print (curr_subset[i])
        }
        return
    }

   // If adding current element increases total_sum above  target_sum, we can reject this solution
    if ( curr_sum + arr[curr_index] <= target_sum )
    {
        curr_subset.add(arr[curr_index])
        curr_sum += arr[curr_index]
        // Include current element in the subset
        subsetSum(arr, target_sum, curr_subset, curr_sum, curr_index + 1)
        curr_subset.pop_back()      // Deleting last element
        curr_sum -= arr[curr_index] // Backtrack
    }

   subsetSum(arr, target_sum, curr_subset, curr_sum, curr_index + 1)
}

Critical ideas to think

• What are the differences between the exhaustive search and backtracking?
• What kind of problems can be solved using these techniques?

Suggested Problems to solve

• Sudoku Solver
• Generate All Parentheses
• Combinations
• Letters combinations of a phone number
• Print all subsets
• N-Queens problem

Happy Coding!