#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-graphs/hamiltonian-flights-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-graphs/hamiltonian-flights-implementation

Repovive

Hamiltonian Flights - Implementation - Mixed Practice: Advanced Graphs | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Hamiltonian Flights - Implementation

Code walkthrough.

function hamiltonianFlights(n, edges):
    adj = adjacency list
    dp = 2D array of size [2^n][n], initialized to 0
    MOD = 10^9 + 7

    dp[1][0] = 1 // Start at city 1, only city 1 visited

    for mask from 1 to 2^n - 1:
        for last from 0 to n-1:
            if not (mask & (1 << last)):
                continue
            if dp[mask][last] == 0:
                continue
            for next in adj[last]:
                if mask & (1 << next):
                    continue
                newMask = mask | (1 << next)
                dp[newMask][next] = (dp[newMask][next] + dp[mask][last]) % MOD

    return dp[(1 << n) - 1][n-1]

Time: $O(n^2 \cdot 2^n)$ . With $n = 20$ , this is about $4 \times 10^8$ operations.

Space complexity is $O(n \cdot 2^n)$ for the data structures used.