Depth-First-Search

Resource: http://blog.csdn.net/u011095253/article/details/9158387

When to use DFS or BFS?

It is heavily depends on the structure of the search tree and the number and the location of the solutions.

• Depends on the depth and width of your solution:
  • BFS is useful for search something in the lowest depth possible
    • ex, finding the shortest path from root to a value; peer-to-peer network, such as finding the nearby location and friend recommendation.
  • DFS is good for searching all the solutions from entire tree, or the path has lowest width but highest depth; usually closely related to backtracking
    • ex. Chess (found all the possibilities); Permutation; All subsets; Combinations;
• BFS usually implement with queue, while DFS usually implement with stack.
• DFS vs. BFS:
  • DFS requires much lower memory than BFS, cause it doesn't necessary store all the children from each level.
• DFS usually combine with backtracking to find all the possible solutions.

Leetcode DFS Collections:

• Basic Permutation, subset:
  • Subset

• 1-dimentional: