Review: DFS Problems Posted on August 12, 2019October 4, 2019 by braindenny Here we try to compile a list of inspiring DFS problems. CheatSheet: Leetcode For Code Interview Basic Abstractions Name Summary dfs avoid duplicate caculations Maintain state array. And update it at the end of dfs Leetcode: Course Schedule Scenarios Code Skeleton Questions Name Example In matrix dfs, change cell to impossible value to avoid state hashmap Leetcode: Word Search II 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: Tree DiameterLeetcode: The Maze IILeetcode: Ternary Expression ParserLeetcode: Surrounded RegionsLeetcode: Sum of Distances in TreeLeetcode: Smallest String Starting From LeafLeetcode: Smallest Rectangle Enclosing Black PixelsLeetcode: Shortest BridgeLeetcode: Remove Invalid ParenthesesLeetcode: Reconstruct ItineraryLeetcode: 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: Most Stones Removed with Same Row or ColumnLeetcode: Minimum Knight MovesLeetcode: MinesweeperLeetcode: 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: Keys and RoomsLeetcode: Island PerimeterLeetcode: Is Graph Bipartite?Leetcode: House Robber IIILeetcode: Generalized AbbreviationLeetcode: Flood FillLeetcode: Evaluate DivisionLeetcode: Escape a Large MazeLeetcode: Employee ImportanceLeetcode: Cousins in Binary TreeLeetcode: Course Schedule IILeetcode: Course ScheduleLeetcode: 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