Backtracking

Backtracking Technique

• Backtracking is a technique that explores multiple paths to find the solution step by step based on some constraints.

Difference between Backtracking and Recursion

• The main difference between backtracking and recursion is that backtracking can avoid exploring all possible paths by pruning branches that do not lead to a solution.

Advantages of Backtracking

• Backtracking is better than brute-force because it avoids exploring all possible paths, which reduces the computational complexity.

Handling Violated Conditions

• If a condition is violated from the required set of conditions, backtracking stops exploring the current path and returns to a previous state to try another path.

Recursive Call Checking

• Recursion provides the option to check the required condition at each possible recursive call.

Applications of Backtracking

• Backtracking is commonly used in constraint satisfaction problems, such as puzzles, games, and scheduling problems.

Exploring All Paths

• A necessary condition to explore all paths while constructing a candidate solution is that the problem must have a finite number of possible solutions.

Example of Backtracking Problem

• An example of a problem that requires backtracking to find a valid path that satisfies certain conditions is the N-Queens problem, where the goal is to place N queens on an NxN chessboard such that no queen attacks another queen.

Palindromic Substrings

• It is necessary to explore all possible ways in which a partitioning can be done to obtain palindromic substrings when finding the longest palindromic substring in a given string.

Pruning Unnecessary Paths

• It is not necessary to check remaining possibilities while constructing a candidate solution when backtracking can prune branches that do not lead to a solution, reducing the computational complexity.