Backtracking

Backtracking is an algorithmic technique that uses brute-force approach to solve a problem.

Brute-force approach states that for any problem, we should try out all possible solutions and pick up those solutions that satisfy the problem constraints.

In backtracking, we build a solution incrementally and follow the approach that if the current solution can’t lead to a valid solution, abandon it and backtrack (or go back) to try another solution. Because of this, recursion becomes a suitable technique for solving backtracking problems.