Review: DFS Problems Posted on August 12, 2019July 26, 2020 by braindenny Here we try to compile a list of inspiring DFS problems. CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups 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 ProblemsLintCode: Word Synthesis ProblemLintCode: Island CityLintCode: Fermat Point Of GraphsLeetCode: Word Search IILeetCode: Word SearchLeetCode: Web CrawlerLeetCode: Univalued Binary TreeLeetCode: Unique Paths IIILeetCode: Two Sum IV – Input is a BSTLeetCode: Tree DiameterLeetCode: The Maze IILeetCode: Ternary Expression ParserLeetCode: Symmetric TreeLeetCode: Surrounded RegionsLeetCode: Sum of Distances in TreeLeetCode: Smallest String Starting From LeafLeetCode: Smallest Rectangle Enclosing Black PixelsLeetCode: Shortest BridgeLeetCode: Remove Sub-Folders from the FilesystemLeetCode: Remove Invalid ParenthesesLeetCode: Reconstruct ItineraryLeetCode: Pseudo-Palindromic Paths in a Binary TreeLeetCode: Populating Next Right Pointers in Each NodeLeetCode: Path SumLeetCode: Pacific Atlantic Water FlowLeetCode: Number of IslandsLeetCode: Number of Distinct Islands IILeetCode: Number of Distinct IslandsLeetCode: Number of Closed IslandsLeetCode: Nested List Weight SumLeetCode: Most Stones Removed with Same Row or ColumnLeetCode: Minimum Time to Collect All Apples in a TreeLeetCode: Minimum Knight MovesLeetCode: Maximum Product of Splitted Binary TreeLeetCode: Maximum Level Sum of a Binary TreeLeetCode: Maximum Depth of N-ary TreeLeetCode: Maximum Average SubtreeLeetCode: Max Area of IslandLeetCode: Making A Large IslandLeetCode: Lowest Common Ancestor of Deepest LeavesLeetCode: Letter Tile PossibilitiesLeetCode: Kill ProcessLeetCode: Keys and RoomsLeetCode: Is Graph Bipartite?LeetCode: House Robber IIILeetCode: Generalized AbbreviationLeetCode: Flood FillLeetCode: Find Leaves of Binary TreeLeetCode: Find All The Lonely NodesLeetCode: Evaluate DivisionLeetCode: Escape a Large MazeLeetCode: Employee ImportanceLeetCode: Cousins in Binary TreeLeetCode: Course Schedule IILeetCode: Course ScheduleLeetCode: Count Good Nodes in Binary TreeLeetCode: Coloring A BorderLeetCode: Clone GraphLeetCode: Binary Tree Right Side ViewLeetCode: Android Unlock PatternsLeetCode: All Paths From Source to TargetLeetCode: All Paths from Source Lead to DestinationLeetCode: 01 Matrix See more blog posts. Post Views: 0