Review: DFS Problems

Posted on August 12, 2019January 26, 2020 by braindenny

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
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

See more blog posts.

Post Views: 0