Backtracking

1. It's usually useful to think of backtracking problem as a depth-first-search problem in a tree. Construct the right tree for different problems.

2. Use recursion to write backtracking program.

3. For storing each solution, there are usually two ways:

   1. Initialize a list (empty or with a given length) before running the helper function, update elements in the list when we process the backtracking. When a path is finished, append this solution to the output.

   2. Add a parameter in the helper function to store the solution we have seen so far. Update this parameter when we process. When a path is finished, append this parameter to the output.

   3. Question 78_Subsets illustrates the two ways.

Note:

1. difference between backtracking and depth first search

   1. Backtracking is a more general purpose algorithm. Depth-First search is a specific form of backtracking related to searching tree structures.

   2. Backtracking is DFS for implicit tree, while DFS is backtracking without pruning.