Introduction
Last updated
Last updated
A backtracking algorithm is a problem-solving algorithm that uses a brute force approach for finding the desired output.
The brute force strategy tests all alternative solutions before selecting the desired/best one. Backtracking implies that if the present answer isn't working, you should go back and try something else.
As a result, recursion is employed in this method. When there are several solutions to a problem, this method is utilised to solve it.
A space state tree is a tree representing all the possible states (solution or nonsolution) of the problem from the root as an initial state to the leaf as a terminal state.
State Space Tree
Problem: You want to find all the possible ways of arranging 2 boys and 1 girl on 3 benches. Constraint: Girl should not be on the middle bench.
Solution: There are a total of 3! = 6 possibilities. We will try all the possibilities and get the possible solutions. We recursively try all the possibilities.
All the possibilities are:
The following state space tree shows the possible solutions.
All the possibilities
State tree with all the solutions
