Backtracking

• used in:
  • Subset problems
  • N Queens Problem
  • Permutation

How to know When to use Backtracking

tip

A general approach to backtracking questions in Java (Subsets Permutations Combination Sum Palindrome Partitioning)

Backtracking Implementation Guide

Backtracking can be solved always as follows:

Pick a starting point.
while(Problem is not solved)
    For each path from the starting point.
        check if selected path is safe, if yes select it
        and make recursive call to rest of the problem
        before which undo the current move.
    End For
If none of the move works out, return false, NO SOLUTON.