Backtracking
What is backtracking? Backtracking is also known as depth-first searching (DFS). DFS is a searching method to traverse a tree-like data structure.
General solution: To solve a problem with DFS, the general procedure contains the two major steps：
- construct a tree-like data structure for the solution space.
- Traversal the tree with appropriate pruning and termination condition.
Common scenario:
combinations and permutations, Soduko solver, 8-Queen problem, 0-1 backpack problem
Practical tips: backtracking = DFS + pruning