This article focuses on introducing Backtracking, including its implementation. It covers the advantages, disadvantages, and various use cases of backtracking.
- What is Backtracking?
As the term suggests, Backtracking involves discarding the current solution to a problem if it is inadequate or unsuitable, then going back (Backtracking) and attempting a different approach. It searches for every possible solution to a problem, essentially by exploring all potential solutions and selecting the most effective one.
Backtracking employs the concept of recursion to explore every possible solution.
Let’s use an example to understand this concept better.
One of the most common problems that can be solved using Backtracking is finding the right path through a maze from one point to another.
How do we tackle this problem in practice?
- We try to move in a particular direction after choosing a route.
- If we reach a point where we cannot proceed towards the goal, we turn around (backtrack) and attempt another route.
Backtracking should be distinguished from the brute-force method. In the brute-force method, we examine every possibility until the very last one, determining whether the result is what we wanted. In contrast, Backtracking stops exploring an option as soon as it becomes clear that it won’t lead to a viable solution. This allows us to reject a choice without pursuing it to the end, saving significant time.
Backtracking is often faster than the brute-force method because it avoids generating and evaluating every potential solution. Instead, it can disqualify many candidates with just one test.
Advantages of Backtracking
- Versatility: Backtracking has a brute-force nature, allowing it to solve a wide range of problems.
- Intuitive Coding: Problems that utilize backtracking are generally intuitive to code.
- Clarity: The step-by-step representation of a backtracking solution is straightforward and easy to understand.
- Ease of Debugging: Backtracking code is usually easy to debug.
- Compact Code: Backtracking implementations often involve fewer lines of code (LOC), typically consisting of a few lines of recursive function code.
Disadvantages of Backtracking
- Speed: Backtracking is relatively slow compared to other methods.
- Inefficiency for Certain Data: Depending on the data, backtracking might conduct an exhaustive search that ultimately yields no valid results.
- High Computational Cost: As a recursive algorithm, backtracking has high computational costs, consuming significant memory and CPU resources.
- High Space Complexity: Due to the use of recursion and stack storage for function calls, backtracking has high space complexity.
For scenarios requiring an efficient algorithm that can handle large volumes of data and find all feasible solutions with fewer computational resources in a shorter time, the branch-and-bound algorithm may be more suitable.
Popular Use Cases of Backtracking
Let’s begin with an introductory problem statement that uses backtracking to arrive at a solution, providing a basic understanding of the concept.
Problem Statement: Given N digits, print all the numbers formed using only the digits 1 and 2. The numbers should be printed in increasing order.
Input 1:
N = 1
Output 1:
1, 2
Input 2:
N = 2
Output 2:
11, 12, 21, 22
Input 3:
N = 3
Output 3:
111, 112, 121, 122, 211, 212, 221, 222
Idea:
If N = 4, we need to fill 4 positions. How can we fill the first position?
The answer is 2, since we have only two digits as options: 1 and 2.
If filling 4 positions is a problem, then filling 3 positions is a subproblem, illustrating the concept of recursion.
Let’s perform a dry run for N = 3. We need to fill 3 positions.
The idea is to try both digits at each index (0th, 1st, and 2nd). As soon as you reach the 3rd index, you can backtrack.
Implementation
Parameters for the function:
- N: The input number of digits.
- arr[N]: An array to store the elements.
- index: To keep track of the current index (when index equals N, print the number and backtrack).
At every index, there are two possible values: 1 and 2, leading to two function calls.
Pseudocode:
function generateNumbers(N, arr, index):
if index == N:
print arr as a number
return
// Assign 1 to the current index and recurse
arr[index] = 1
generateNumbers(N, arr, index + 1)
// Assign 2 to the current index and recurse
arr[index] = 2
generateNumbers(N, arr, index + 1)Here is the breakdown of the process:
- If the current index equals N, print the number formed by the array
arrand backtrack. - Assign the digit 1 to the current index and call the function recursively for the next index.
- Assign the digit 2 to the current index and call the function recursively for the next index.
class Main
{
public static void printAll(int[] arr, int n, int index){
if(index == n){
print(arr);
System.out.println();
return;
}
arr[index] = 1; //first put ‘1’ in 0th index
printAll(arr, n, index + 1); //function call for next index
arr[index] = 2; //after all the outputs statring with 1, try ‘2’ in 0th index
printAll(arr, n, index + 1); //function call for next index
}
public static void main(String args[]){
int n = 3;
//read n
int[] arr = new int[n];
printAll(arr, n, 0);
}
public static void print(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i] + " ");
}
}}
Output:
111
112
121
122
211
212
221
222
Conclusion
Backtracking is a versatile algorithmic technique commonly used in data structures to solve problems recursively by exploring various possible solutions and undoing them if they do not lead to a viable solution. If you enjoyed this article, please like it and share it with your friends.
Read More…
Backracking | Data Structures & Algorithms Tutorials – https://kamleshsingad.com/backracking-data-structures-algorithms-tutorials/
What is Dynamic Programming? Working, Algorithms, and Examples – https://kamleshsingad.com/what-is-dynamic-programming-working-algorithms-and-examples/
Greedy Algorithm – https://kamleshsingad.com/greedy-algorithm/
