Algorithm -- Backtracking

Backtracking is a brute-force search algorithm with pruning. The main algorithm often uses DFS to go deep to try if the solution can stay true till the end to meet target.

A typical framework is

• Need a result list and levelList for each result
• The major loop will do scan over available elements(like Array, a group of arrays, set. etc.)
• The recursion needs to transfer level/pos information to next level

Some variations are frequently used

1. original data has dup or no dup ?  --> use standard (i>0 && n[i]==n[i-1]) to skip dup 
2. original data order is significant ? --> use full scan loop or incremental scan from pos+1
3. final result should be be ordered like non-descending ? -- sort first 
4. result can have dup, no dup inside ? --> use levelList.contains() to uniquify
5. track the current used pool ? visited[] flag vs hashset()
6. result must include all elements ? --> subset/combination vs permutation 

Typical example is combination, subset permutation Some famous ones are NQueen Break IP address PhoneLetterCombination