Here we try to compile a list of inspiring DFS problems.

**Basic Abstractions**

Name | Summary |
---|---|

dfs avoid duplicate caculations | Maintain state array. And update it at the end of dfs LeetCode: Course Schedule |

For backtracking in DFS | When and what to do backtracking |

**Scenarios**

**Code Skeleton**

**Top Questions**

Name | Example |
---|---|

In matrix dfs, change cell to impossible value to avoid state hashmap | LeetCode: Word Search II |

In matrix dfs, when to change and restore cell state? |

- dfs get results from return value or input parameters

// https://code.dennyzhang.com/android-unlock-patterns func dfs(pos int, visited []bool, count int, middles [][]int) int { // find one path if count == 0 { return 1 } res := 0 visited[pos] = true for i:=1; i<=9; i++ { if !visited[i] { // from pos -> to: adjacent or the middle node visited if middles[pos][i] == 0|| visited[middles[pos][i]] { res += dfs(i, visited, count-1, middles) } } } // backtracking visited[pos] = false return res }

// https://code.dennyzhang.com/android-unlock-patterns func dfs(pos int, visited []bool, count int, middles [][]int, res *int) { // find one path if count == 0 { *res += 1 } visited[pos] = true for i:=1; i<=9; i++ { if !visited[i] { // from pos -> to: adjacent or the middle node visited if middles[pos][i] == 0|| visited[middles[pos][i]] { dfs(i, visited, count-1, middles, res) } } } // backtracking visited[pos] = false }

See all dfs problems: #dfs

- Review: DFS Problems
- LintCode: Word Synthesis Problem
- LintCode: Island City
- LintCode: Fermat Point Of Graphs
- LeetCode: Word Search II
- LeetCode: Word Search
- LeetCode: Web Crawler
- LeetCode: Univalued Binary Tree
- LeetCode: Unique Paths III
- LeetCode: Two Sum IV – Input is a BST
- LeetCode: Tree Diameter
- LeetCode: The Maze II
- LeetCode: Ternary Expression Parser
- LeetCode: Symmetric Tree
- LeetCode: Surrounded Regions
- LeetCode: Sum of Distances in Tree
- LeetCode: Smallest String Starting From Leaf
- LeetCode: Smallest Rectangle Enclosing Black Pixels
- LeetCode: Shortest Bridge
- LeetCode: Remove Sub-Folders from the Filesystem
- LeetCode: Remove Invalid Parentheses
- LeetCode: Reconstruct Itinerary
- LeetCode: Pseudo-Palindromic Paths in a Binary Tree
- LeetCode: Populating Next Right Pointers in Each Node
- LeetCode: Path Sum
- LeetCode: Pacific Atlantic Water Flow
- LeetCode: Number of Islands
- LeetCode: Number of Distinct Islands II
- LeetCode: Number of Distinct Islands
- LeetCode: Number of Closed Islands
- LeetCode: Nested List Weight Sum
- LeetCode: Most Stones Removed with Same Row or Column
- LeetCode: Minimum Time to Collect All Apples in a Tree
- LeetCode: Minimum Knight Moves
- LeetCode: Maximum Product of Splitted Binary Tree
- LeetCode: Maximum Level Sum of a Binary Tree
- LeetCode: Maximum Depth of N-ary Tree
- LeetCode: Maximum Average Subtree
- LeetCode: Max Area of Island
- LeetCode: Making A Large Island
- LeetCode: Lowest Common Ancestor of Deepest Leaves
- LeetCode: Letter Tile Possibilities
- LeetCode: Kill Process
- LeetCode: Keys and Rooms
- LeetCode: Is Graph Bipartite?
- LeetCode: House Robber III
- LeetCode: Generalized Abbreviation
- LeetCode: Flood Fill
- LeetCode: Find Leaves of Binary Tree
- LeetCode: Find All The Lonely Nodes
- LeetCode: Evaluate Division
- LeetCode: Escape a Large Maze
- LeetCode: Employee Importance
- LeetCode: Cousins in Binary Tree
- LeetCode: Course Schedule II
- LeetCode: Course Schedule
- LeetCode: Count Good Nodes in Binary Tree
- LeetCode: Coloring A Border
- LeetCode: Clone Graph
- LeetCode: Binary Tree Right Side View
- LeetCode: Android Unlock Patterns
- LeetCode: All Paths From Source to Target
- LeetCode: All Paths from Source Lead to Destination
- LeetCode: 01 Matrix

See more blog posts.