Backtracking Method in DAA

Learn Backtracking Method in DAA with its definition, working process, general algorithm, advantages, disadvantages, and applications like N-Queens, Graph Coloring, Hamiltonian Cycle, and Subset Sum.

Backtracking Method in DAA

Introduction

Some problems cannot be solved using simple and straightforward techniques such as Greedy or Divide and Conquer.
In such problems, it becomes necessary to explore all possible solutions in a systematic manner.

The technique used to solve such problems is called Backtracking.

What is Backtracking?

Backtracking is a systematic search technique in which:

• A partial solution is constructed at each step
• If the partial solution does not lead to a valid solution, the algorithm goes back (backtracks) and tries another alternative

Try → Check → If fails → Go back → Try another

Need for Backtracking

(Limitations of Algorithmic Power)**

• Some problems cannot be solved in Polynomial Time
• It is necessary to check all possible combinations
• Such problems generally belong to NP-Complete or NP-Hard categories

Examples:

• N-Queens Problem
• Graph Coloring
• Hamiltonian Cycle
• Subset Sum Problem

How Does Backtracking Work?

1. The problem is represented in the form of a Decision Tree
2. Each node of the tree represents a partial solution
3. If a node is found to be invalid, that branch is discarded (Pruning)
4. The process continues until a correct solution is found or all possibilities are exhausted

Backtracking Algorithm – General Form

Backtrack(solution)
{
if (solution is complete)
print solution
else
select next option
if (option is valid)
Backtrack(new solution)
}

Advantages of Backtracking

• All possible solutions can be explored
• Useful for solving complex and constraint-based problems
• Guarantees correctness of the solution

Disadvantages of Backtracking

• Time complexity is very high
• Inefficient for large input sizes
• Requires exponential time in the worst case

Major Applications of Backtracking

Conclusion

• Backtracking is an effective but computationally expensive technique.
• It is useful in situations where other algorithmic methods fail.
• This method clearly demonstrates the limitations of algorithmic power.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1