Graph Algorithms

Euler & Hamilton Paths (Hierholzer, Held-Karp)

Table of Contents

Euler paths (visiting every edge once) can be found in linear time, while Hamilton paths (visiting every vertex once) are NP-complete. This guide covers Hierholzer's algorithm, bitmask DP, and the Held-Karp approach.

The Konigsberg Bridge Problem

In 1736, Leonhard Euler tackled a famous puzzle: Can you walk through the city of Konigsberg, crossing each of its seven bridges exactly once? The city was built on the Pregel River with two islands, connected by seven bridges.

A North Bank B South Bank C Island 1 D Island 2 b1 b2 b3 b4 b5 b6 b7

Euler modeled this as a multigraph where land masses are vertices and bridges are edges:

A B C D deg=3 deg=3 deg=5 deg=3

Every vertex has odd degree: A(3), B(3), C(5), D(3). Euler proved that a walk crossing every edge exactly once is impossible because more than two vertices have odd degree. This was the birth of graph theory.

Euler Paths and Circuits

Definitions

  • Euler Path (Trail): A path that visits every edge of the graph exactly once. Vertices may be revisited.
  • Euler Circuit (Tour): An Euler path that starts and ends at the same vertex (a closed walk visiting every edge exactly once).
  • Eulerian Graph: A graph that contains an Euler circuit.
  • Semi-Eulerian Graph: A graph that contains an Euler path but not an Euler circuit.

The key distinction from Hamilton paths: Euler cares about edges, Hamilton cares about vertices.

Euler Path example on a graph with 5 vertices and 6 edges:

  A --- B --- C
  |   / |   /
  |  /  |  /
  | /   | /
  D --- E

Euler path: A -> D -> B -> A (wait -- this doesn't use all edges)
Correct Euler path: A -> B -> C -> E -> B -> D -> A
Every edge used exactly once. Vertex B visited 3 times.

Euler's Theorem -- Existence Conditions

Undirected Graphs

Euler's Theorem (1736): For a connected undirected graph G:

  1. G has an Euler circuit if and only if every vertex has even degree.
  2. G has an Euler path (but not a circuit) if and only if exactly two vertices have odd degree. These two vertices must be the start and end of the path.
  3. If more than two vertices have odd degree, no Euler path exists.

Proof of necessity (Euler circuit):

Consider any Euler circuit. Every time the walk enters a vertex through some edge, it must leave through a different edge (since no edge is repeated). So edges at each vertex are paired into enter/leave pairs. This means every vertex uses an even number of edges, so every vertex has even degree.

For the start vertex in an Euler circuit, we leave first (using one edge), then every subsequent visit uses one enter + one leave edge, and finally we return (one more enter). Total: 1 (initial leave) + 2k (enter/leave pairs for k revisits) + 1 (final enter) = 2k + 2, which is even.

Proof of sufficiency (Euler circuit):

This is more subtle. We prove it constructively using Hierholzer's algorithm (covered next). The key insight:

  1. Start at any vertex and follow edges (removing them as you go) until you get stuck. Because every vertex has even degree, whenever you enter a vertex there must be an unused edge to leave -- except at the start vertex. So you always get stuck at the start vertex, forming a circuit.
  2. If this circuit does not cover all edges, some vertex on the circuit has unused edges. Start a new sub-circuit from there. Since we removed the first circuit's edges and the original graph had all even degrees, the remaining graph also has all even degrees, so the sub-circuit argument applies recursively.
  3. Splice the sub-circuits together to form the full Euler circuit.

Proof of the Euler path case:

If exactly two vertices u and v have odd degree, add a virtual edge (u, v). Now all vertices have even degree, so an Euler circuit exists. Remove the virtual edge from the circuit to get an Euler path from u to v.

Directed Graphs

For a connected directed graph G:

  1. G has an Euler circuit if and only if every vertex has equal in-degree and out-degree: deg_in(v) = deg_out(v) for all v.
  2. G has an Euler path if and only if at most one vertex has out_degree - in_degree = 1 (the start), at most one vertex has in_degree - out_degree = 1 (the end), and all other vertices have equal in-degree and out-degree.
Graph Type Euler Circuit Condition Euler Path Condition Undirected All vertices have even degree Exactly 2 vertices have odd degree Directed in(v) = out(v) for all v One vertex: out - in = 1 One vertex: in - out = 1 All others: in = out Both Graph must be connected Graph must be connected (weakly connected for directed) (weakly connected for directed)

Checking Existence in Code

#include <bits/stdc++.h>
using namespace std;

// Check Euler path/circuit existence in an undirected graph
// Returns: 0 = none, 1 = Euler path, 2 = Euler circuit
int checkEulerUndirected(int n, vector<vector<int>>& adj) {
    // Check connectivity (ignore isolated vertices)
    vector<bool> visited(n, false);
    int start = -1;
    for (int i = 0; i < n; i++) {
        if (!adj[i].empty()) { start = i; break; }
    }
    if (start == -1) return 2; // no edges = trivially Eulerian

    // BFS/DFS to check connectivity
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!adj[i].empty() && !visited[i]) return 0; // disconnected
    }

    // Count odd-degree vertices
    int oddCount = 0;
    for (int i = 0; i < n; i++) {
        if (adj[i].size() % 2 != 0) oddCount++;
    }

    if (oddCount == 0) return 2;       // Euler circuit
    if (oddCount == 2) return 1;       // Euler path
    return 0;                           // no Euler path
}

// Check Euler path/circuit existence in a directed graph
// Returns: 0 = none, 1 = Euler path, 2 = Euler circuit
int checkEulerDirected(int n, vector<vector<int>>& adj) {
    vector<int> inDeg(n, 0), outDeg(n, 0);
    for (int u = 0; u < n; u++) {
        outDeg[u] = adj[u].size();
        for (int v : adj[u]) inDeg[v]++;
    }

    // Check weak connectivity (treat as undirected)
    vector<vector<int>> undirected(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) {
            undirected[u].push_back(v);
            undirected[v].push_back(u);
        }
    vector<bool> visited(n, false);
    int start = -1;
    for (int i = 0; i < n; i++) {
        if (inDeg[i] + outDeg[i] > 0) { start = i; break; }
    }
    if (start == -1) return 2;

    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : undirected[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if ((inDeg[i] + outDeg[i] > 0) && !visited[i]) return 0;
    }

    // Check degree conditions
    int startNodes = 0, endNodes = 0;
    for (int i = 0; i < n; i++) {
        int diff = outDeg[i] - inDeg[i];
        if (diff == 0) continue;
        else if (diff == 1) startNodes++;
        else if (diff == -1) endNodes++;
        else return 0; // impossible
    }

    if (startNodes == 0 && endNodes == 0) return 2;  // Euler circuit
    if (startNodes == 1 && endNodes == 1) return 1;   // Euler path
    return 0;
}

Time Complexity: O(V + E) for both checks.

Hierholzer's Algorithm

Hierholzer's algorithm (1873) finds an Euler circuit or path in O(V + E) time. It is the standard algorithm used in competitive programming and interviews.

Intuition -- Why It Works

The algorithm is based on two observations:

  1. Following edges greedily forms a circuit. Start at any vertex and keep walking along unused edges. Because all vertices have even degree (for Euler circuit), you can never get stuck at a non-start vertex -- if you entered it, there must be an unused edge to leave. You always return to the start.

  2. If the circuit misses edges, splice in sub-circuits. The greedy circuit might not use all edges. But any vertex on the circuit that still has unused edges can serve as the start of another sub-circuit. We splice these together.

The elegant implementation uses a DFS with post-order recording. Instead of explicitly finding circuits and splicing them, we let the recursive DFS handle it:

DFS(u):
    while u has unused outgoing edges:
        pick an unused edge (u, v)
        mark edge as used
        DFS(v)
    append u to result (front)

The key insight is the post-order recording: we add a vertex to the path only after we have exhausted all edges from it. This naturally handles the "splicing" -- when we reach a dead end (all edges from current vertex are used), we record that vertex and backtrack to continue exploring unused edges.

Step-by-Step Walkthrough

Consider this directed graph with 4 vertices and 6 edges:

Directed Graph (all in-deg = out-deg) 0 1 2 3 e1 e2 e3 e4 e5 e6 Vertex 0: in=2, out=2 Vertex 1: in=1, out=1 Vertex 2: in=2, out=2 Vertex 3: in=1, out=1

Adjacency lists (sorted): 0->[1,2], 1->[2], 2->[0,3], 3->[0]

Hierholzer's DFS Trace (starting from vertex 0):

DFS(0):
  Edge 0->1 (take it, mark used)
  DFS(1):
    Edge 1->2 (take it, mark used)
    DFS(2):
      Edge 2->0 (take it, mark used)
      DFS(0):
        Edge 0->2 (take it, mark used) [0->1 already used]
        DFS(2):
          Edge 2->3 (take it, mark used) [2->0 already used]
          DFS(3):
            Edge 3->0 (take it, mark used)
            DFS(0):
              No unused edges from 0
              append 0 to front -> result: [0]
            append 3 to front -> result: [3, 0]
          append 2 to front -> result: [2, 3, 0]
        append 0 to front -> result: [0, 2, 3, 0]
      append 2 to front -> result: [2, 0, 2, 3, 0]
    append 1 to front -> result: [1, 2, 0, 2, 3, 0]
  append 0 to front -> result: [0, 1, 2, 0, 2, 3, 0]

Euler circuit: 0 -> 1 -> 2 -> 0 -> 2 -> 3 -> 0
All 6 edges used exactly once!

Notice how the algorithm naturally "spliced" two circuits: the inner circuit (0->2->3->0) was discovered while exploring from vertex 0 during the outer circuit (0->1->2->0).

C++ Implementation -- Directed Graph

#include <bits/stdc++.h>
using namespace std;

class EulerCircuitDirected {
    int n;
    vector<vector<int>> adj;
    vector<int> idx; // current edge index for each vertex
    vector<int> path;

    void dfs(int u) {
        while (idx[u] < (int)adj[u].size()) {
            int v = adj[u][idx[u]++]; // take next unused edge
            dfs(v);
        }
        path.push_back(u); // post-order: add after all edges exhausted
    }

public:
    // adj[u] contains all vertices v such that edge u->v exists
    // (may contain duplicates for multigraphs)
    vector<int> findEulerCircuit(int n_, vector<vector<int>>& adj_) {
        n = n_;
        adj = adj_;
        idx.assign(n, 0);
        path.clear();

        // Verify Euler circuit exists
        vector<int> inDeg(n, 0);
        for (int u = 0; u < n; u++)
            for (int v : adj[u])
                inDeg[v]++;
        for (int i = 0; i < n; i++)
            if (inDeg[i] != (int)adj[i].size())
                return {}; // in-degree != out-degree

        // Find a vertex with edges
        int start = -1;
        for (int i = 0; i < n; i++)
            if (!adj[i].empty()) { start = i; break; }
        if (start == -1) return {0}; // no edges

        dfs(start);
        reverse(path.begin(), path.end());

        // Verify all edges were used
        int totalEdges = 0;
        for (int u = 0; u < n; u++) totalEdges += adj[u].size();
        if ((int)path.size() != totalEdges + 1) return {}; // disconnected

        return path;
    }

    // For Euler path (not circuit): find start vertex with out-in=1
    vector<int> findEulerPath(int n_, vector<vector<int>>& adj_) {
        n = n_;
        adj = adj_;
        idx.assign(n, 0);
        path.clear();

        vector<int> inDeg(n, 0);
        for (int u = 0; u < n; u++)
            for (int v : adj[u])
                inDeg[v]++;

        int start = -1, end = -1;
        int startCount = 0, endCount = 0;
        for (int i = 0; i < n; i++) {
            int diff = (int)adj[i].size() - inDeg[i];
            if (diff == 1) { start = i; startCount++; }
            else if (diff == -1) { end = i; endCount++; }
            else if (diff != 0) return {};
        }

        if (startCount == 0 && endCount == 0) {
            // All balanced -> Euler circuit, start anywhere
            for (int i = 0; i < n; i++)
                if (!adj[i].empty()) { start = i; break; }
        } else if (startCount != 1 || endCount != 1) {
            return {};
        }

        if (start == -1) return {};

        dfs(start);
        reverse(path.begin(), path.end());

        int totalEdges = 0;
        for (int u = 0; u < n; u++) totalEdges += adj[u].size();
        if ((int)path.size() != totalEdges + 1) return {};

        return path;
    }
};

int main() {
    // Example: directed graph with Euler circuit
    int n = 4;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {2};
    adj[2] = {0, 3};
    adj[3] = {0};

    EulerCircuitDirected solver;
    vector<int> circuit = solver.findEulerCircuit(n, adj);
    for (int v : circuit) cout << v << " ";
    // Output: 0 1 2 0 2 3 0
    cout << "\n";
    return 0;
}

Time Complexity: O(V + E). Each edge is visited exactly once by the DFS. The idx array ensures we never re-scan already-used edges.

Space Complexity: O(V + E) for adjacency lists and recursion stack.

C++ Implementation -- Undirected Graph

Undirected graphs require extra care: when we traverse edge (u, v), we must also mark the reverse edge (v, u) as used. We do this by pairing edges: edge i and edge i^1 are reverse pairs (using XOR trick with even/odd indexing).

#include <bits/stdc++.h>
using namespace std;

class EulerCircuitUndirected {
    int n;
    vector<vector<pair<int,int>>> adj; // adj[u] = {(v, edge_id), ...}
    vector<bool> usedEdge;
    vector<int> idx;
    vector<int> path;

    void dfs(int u) {
        while (idx[u] < (int)adj[u].size()) {
            auto [v, eid] = adj[u][idx[u]++];
            if (usedEdge[eid]) continue; // edge already used
            usedEdge[eid] = true;
            dfs(v);
        }
        path.push_back(u);
    }

public:
    // edges: list of (u, v) pairs (undirected)
    vector<int> findEulerCircuit(int n_, vector<pair<int,int>>& edges) {
        n = n_;
        adj.assign(n, {});
        int m = edges.size();
        usedEdge.assign(m, false);
        idx.assign(n, 0);
        path.clear();

        for (int i = 0; i < m; i++) {
            auto [u, v] = edges[i];
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        // Check all vertices have even degree
        for (int i = 0; i < n; i++)
            if (adj[i].size() % 2 != 0) return {};

        int start = -1;
        for (int i = 0; i < n; i++)
            if (!adj[i].empty()) { start = i; break; }
        if (start == -1) return {0};

        dfs(start);
        reverse(path.begin(), path.end());

        if ((int)path.size() != m + 1) return {}; // not all edges used

        return path;
    }

    vector<int> findEulerPath(int n_, vector<pair<int,int>>& edges) {
        n = n_;
        adj.assign(n, {});
        int m = edges.size();
        usedEdge.assign(m, false);
        idx.assign(n, 0);
        path.clear();

        for (int i = 0; i < m; i++) {
            auto [u, v] = edges[i];
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        // Find vertices with odd degree
        int start = -1;
        int oddCount = 0;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() % 2 != 0) {
                oddCount++;
                if (start == -1) start = i;
            }
        }

        if (oddCount != 0 && oddCount != 2) return {};
        if (start == -1) {
            for (int i = 0; i < n; i++)
                if (!adj[i].empty()) { start = i; break; }
        }
        if (start == -1) return {0};

        dfs(start);
        reverse(path.begin(), path.end());

        if ((int)path.size() != m + 1) return {};
        return path;
    }
};

int main() {
    // Triangle graph: 0-1, 1-2, 2-0
    int n = 3;
    vector<pair<int,int>> edges = {{0,1}, {1,2}, {2,0}};

    EulerCircuitUndirected solver;
    vector<int> circuit = solver.findEulerCircuit(n, edges);
    for (int v : circuit) cout << v << " ";
    // Output: 0 1 2 0
    cout << "\n";
    return 0;
}

Critical detail for undirected graphs: We use a shared usedEdge boolean array indexed by edge ID. Both directions of the same undirected edge share the same edge ID, so traversing (u,v) automatically prevents traversing (v,u).

Time Complexity: O(V + E). The idx[u] pointer and usedEdge check together ensure amortized O(1) per edge.

Space Complexity: O(V + E).

Fleury's Algorithm

Fleury's algorithm (1883) is a simpler but slower approach to finding Euler paths. The idea is:

  1. Start at a valid vertex (odd-degree vertex for Euler path, any vertex for circuit).
  2. At each step, choose an edge to traverse. Prefer non-bridge edges -- only cross a bridge if there is no alternative.
  3. Remove the traversed edge and continue.

Why Avoid Bridges?

A bridge is an edge whose removal disconnects the graph. If you cross a bridge prematurely, you may strand some edges on the disconnected side, making it impossible to complete the Euler path.

Pseudocode

Fleury(G, start):
    path = [start]
    current = start
    while current has adjacent edges:
        if current has only one adjacent edge (u, v):
            traverse it, remove it
        else:
            pick an edge (current, v) that is NOT a bridge
            traverse it, remove it
        current = v
        path.append(v)
    return path

Complexity Comparison

Algorithm Time Space Notes Hierholzer's O(V + E) O(V + E) Preferred Fleury's O(E^2) O(V + E) Simpler to understand, impractical for large E

Fleury's algorithm is O(E^2) because at each of the E steps, we may need O(E) time to check whether an edge is a bridge (using DFS or Tarjan's bridge-finding). While the bridge check can be optimized, Hierholzer's algorithm is strictly superior in practice.

Interview tip: Know that Fleury's exists and its O(E^2) complexity, but always implement Hierholzer's.

Chinese Postman Problem

The Chinese Postman Problem (also called the Route Inspection Problem) asks: what is the minimum total weight of a closed walk that traverses every edge at least once?

When the Graph is Eulerian

If the graph has an Euler circuit (all vertices have even degree), the answer is simply the sum of all edge weights -- the Euler circuit visits each edge exactly once.

When the Graph is Not Eulerian

If some vertices have odd degree, we must "duplicate" some edges (traverse them more than once) to make all degrees even. The goal is to minimize the total weight of duplicated edges.

Key observations:

  1. By the Handshaking Lemma, the number of odd-degree vertices is always even.
  2. We need to add edges between odd-degree vertices to make all degrees even.
  3. This reduces to a minimum weight perfect matching on the odd-degree vertices.

Algorithm

  1. Find all vertices with odd degree. Call this set S (|S| is always even).
  2. Compute shortest paths between all pairs of vertices in S.
  3. Find a minimum weight perfect matching on S using these distances.
  4. Answer = (sum of all edge weights) + (weight of the matching).

For general graphs, minimum weight perfect matching can be solved in O(V^3) using Edmonds' blossom algorithm. In practice for interview problems, |S| is often small enough for bitmask DP.

#include <bits/stdc++.h>
using namespace std;

// Chinese Postman for undirected weighted graph
// Returns minimum total distance to traverse every edge at least once
long long chinesePostman(int n, vector<tuple<int,int,int>>& edges) {
    // Build adjacency list
    vector<vector<pair<int,int>>> adj(n);
    long long totalWeight = 0;
    vector<int> degree(n, 0);

    for (auto& [u, v, w] : edges) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        degree[u]++;
        degree[v]++;
        totalWeight += w;
    }

    // Find odd-degree vertices
    vector<int> odd;
    for (int i = 0; i < n; i++)
        if (degree[i] % 2 != 0) odd.push_back(i);

    if (odd.empty()) return totalWeight; // already Eulerian

    int k = odd.size(); // always even

    // Compute shortest paths between all odd-degree vertices using Dijkstra
    vector<vector<long long>> dist(k, vector<long long>(k, LLONG_MAX));
    for (int i = 0; i < k; i++) {
        // Dijkstra from odd[i]
        vector<long long> d(n, LLONG_MAX);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>,
                       greater<>> pq;
        d[odd[i]] = 0;
        pq.push({0, odd[i]});
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du > d[u]) continue;
            for (auto [v, w] : adj[u]) {
                if (d[u] + w < d[v]) {
                    d[v] = d[u] + w;
                    pq.push({d[v], v});
                }
            }
        }
        for (int j = 0; j < k; j++)
            dist[i][j] = d[odd[j]];
    }

    // Minimum weight perfect matching via bitmask DP
    // dp[mask] = min cost to match all vertices in mask
    int full = (1 << k) - 1;
    vector<long long> dp(1 << k, LLONG_MAX);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << k); mask++) {
        if (dp[mask] == LLONG_MAX) continue;
        // Find first unmatched vertex
        int i = -1;
        for (int b = 0; b < k; b++) {
            if (!(mask & (1 << b))) { i = b; break; }
        }
        if (i == -1) continue;
        // Try matching it with every other unmatched vertex
        for (int j = i + 1; j < k; j++) {
            if (mask & (1 << j)) continue;
            int newMask = mask | (1 << i) | (1 << j);
            dp[newMask] = min(dp[newMask], dp[mask] + dist[i][j]);
        }
    }

    return totalWeight + dp[full];
}

int main() {
    int n = 4;
    vector<tuple<int,int,int>> edges = {
        {0, 1, 1}, {1, 2, 2}, {2, 3, 3}, {3, 0, 4}, {0, 2, 5}
    };
    cout << chinesePostman(n, edges) << "\n"; // 18
    return 0;
}

Time Complexity:

  • Dijkstra for each odd vertex: O(k * (V + E) log V)
  • Bitmask DP for matching: O(2^k * k)
  • Total: O(k * (V + E) log V + 2^k * k) where k = number of odd-degree vertices

Hamilton Paths and Circuits

Definitions

  • Hamilton Path: A path that visits every vertex of the graph exactly once.
  • Hamilton Circuit (Cycle): A Hamilton path that returns to the starting vertex.
  • Hamiltonian Graph: A graph that contains a Hamilton circuit.
Euler Path Every EDGE once, vertices repeat OK A B C D E Hamilton Path Every VERTEX once, edges skip OK A B C D E

NP-Completeness

Determining whether a Hamilton path exists in a general graph is NP-complete. This is one of Karp's original 21 NP-complete problems (1972).

Why is this so different from Euler paths?

  • Euler paths have a clean characterization (vertex degree conditions) that can be checked in O(V + E). The structure of edges is "local" -- each edge's contribution to vertex degrees is independent.
  • Hamilton paths have no known efficient characterization. You cannot determine existence by looking at local properties like vertex degrees. The problem requires reasoning about global structure -- how all vertices connect together.

Intuition for the difficulty: To check if an Euler path exists, we just count degrees -- a purely local operation. For Hamilton paths, we essentially need to determine if a specific combinatorial structure exists among all possible orderings of vertices. There are n! possible orderings, and no known shortcut avoids exponential search.

Some sufficient conditions (but not necessary):

  • Dirac's Theorem (1952): If every vertex in an n-vertex graph (n >= 3) has degree >= n/2, then the graph has a Hamilton circuit.
  • Ore's Theorem (1960): If for every pair of non-adjacent vertices u, v we have deg(u) + deg(v) >= n, then the graph has a Hamilton circuit.
  • Complete graphs K_n (n >= 3) are always Hamiltonian.

These give sufficient conditions but cannot tell you a graph does NOT have a Hamilton path.

Solving Hamilton Path -- Backtracking

The most straightforward approach is backtracking: try all possible paths, pruning when we get stuck.

Algorithm

backtrack(current_vertex, visited_set, path_length):
    if path_length == n:
        found Hamilton path!
        return true
    for each neighbor v of current_vertex:
        if v not in visited_set:
            mark v as visited
            if backtrack(v, visited_set, path_length + 1):
                return true
            unmark v
    return false

Complete C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class HamiltonPathBacktracking {
    int n;
    vector<vector<int>> adj;
    vector<bool> visited;
    vector<int> path;

    bool backtrack(int u, int count) {
        if (count == n) return true; // all vertices visited

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                path.push_back(v);
                if (backtrack(v, count + 1)) return true;
                path.pop_back();
                visited[v] = false;
            }
        }
        return false;
    }

public:
    // Returns a Hamilton path if one exists, empty vector otherwise
    vector<int> findHamiltonPath(int n_, vector<vector<int>>& adj_) {
        n = n_;
        adj = adj_;
        visited.assign(n, false);

        // Try starting from each vertex
        for (int start = 0; start < n; start++) {
            visited[start] = true;
            path = {start};
            if (backtrack(start, 1)) return path;
            visited[start] = false;
        }
        return {}; // no Hamilton path exists
    }

    // Check if Hamilton circuit exists
    bool hasHamiltonCircuit(int n_, vector<vector<int>>& adj_) {
        n = n_;
        adj = adj_;
        visited.assign(n, false);

        // Fix start vertex as 0 (circuit is a cycle, so start doesn't matter)
        visited[0] = true;
        path = {0};
        return backtrackCircuit(0, 1);
    }

private:
    bool backtrackCircuit(int u, int count) {
        if (count == n) {
            // Check if there's an edge back to start
            for (int v : adj[u])
                if (v == 0) return true;
            return false;
        }
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                path.push_back(v);
                if (backtrackCircuit(v, count + 1)) return true;
                path.pop_back();
                visited[v] = false;
            }
        }
        return false;
    }
};

int main() {
    // Pentagon graph: 0-1-2-3-4-0 with diagonal 0-2
    int n = 5;
    vector<vector<int>> adj(n);
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    addEdge(0,1); addEdge(1,2); addEdge(2,3);
    addEdge(3,4); addEdge(4,0); addEdge(0,2);

    HamiltonPathBacktracking solver;
    vector<int> path = solver.findHamiltonPath(n, adj);
    if (!path.empty()) {
        cout << "Hamilton path: ";
        for (int v : path) cout << v << " ";
        cout << "\n"; // e.g., 1 0 2 3 4
    }
    return 0;
}

Time Complexity: O(n! * n) in the worst case. For each of the n starting vertices, we explore up to (n-1)! permutations, each taking O(n) to process.

Space Complexity: O(n) for the recursion stack and visited array.

When to use backtracking: Only when n is very small (n <= 15-20). For n = 20, n! = 2.4 * 10^18 which is far too slow, but heavy pruning often makes it feasible for sparse graphs.

Solving Hamilton Path -- Bitmask DP (Held-Karp)

The Held-Karp algorithm (1962) uses dynamic programming with bitmasks to solve Hamilton path and the Travelling Salesman Problem (TSP) in O(2^n * n^2) time, dramatically faster than O(n!) backtracking.

Key Insight

Instead of tracking the exact order of vertices visited, we only track:

  1. Which vertices have been visited (a bitmask of n bits)
  2. Which vertex we are currently at

This gives n * 2^n states instead of n! permutations.

State Definition

dp[mask][i] = can we visit exactly the set of vertices in `mask`,
              ending at vertex i?

For TSP (minimum cost):
dp[mask][i] = minimum cost to visit exactly the vertices in `mask`,
              starting from vertex 0 and ending at vertex i

Transitions

For each state (mask, i) where dp[mask][i] is valid:
    For each neighbor j of i where j is NOT in mask:
        dp[mask | (1 << j)][j] = dp[mask][i] + cost(i, j)

Walkthrough

Consider a 4-vertex graph: 0-1, 1-2, 2-3, 0-3, 0-2

Finding Hamilton path using bitmask DP:

States: dp[mask][i] = true if we can visit vertices in mask, ending at i

Base cases (single vertices):
  dp[0001][0] = true   (only vertex 0 visited, at vertex 0)
  dp[0010][1] = true   (only vertex 1 visited, at vertex 1)
  dp[0100][2] = true
  dp[1000][3] = true

Expanding from dp[0001][0]:
  0 has neighbors 1, 2, 3
  dp[0011][1] = true   (visited {0,1}, at vertex 1)
  dp[0101][2] = true   (visited {0,2}, at vertex 2)
  dp[1001][3] = true   (visited {0,3}, at vertex 3)

Expanding from dp[0011][1]:
  1 has neighbors 0(visited), 2
  dp[0111][2] = true   (visited {0,1,2}, at vertex 2)

Expanding from dp[0111][2]:
  2 has neighbors 0(visited), 1(visited), 3
  dp[1111][3] = true   (visited {0,1,2,3}, at vertex 3)

mask = 1111 = all visited! Hamilton path exists: 0 -> 1 -> 2 -> 3

Complete C++ Implementation -- Hamilton Path Existence

#include <bits/stdc++.h>
using namespace std;

// Check if Hamilton path exists, and reconstruct it
// O(2^n * n^2) time, O(2^n * n) space
vector<int> findHamiltonPathBitmask(int n, vector<vector<int>>& adj) {
    // dp[mask][i] = true if we can visit exactly the vertices in mask,
    // ending at vertex i
    vector<vector<bool>> dp(1 << n, vector<bool>(n, false));
    vector<vector<int>> parent(1 << n, vector<int>(n, -1));

    // Base case: start at any single vertex
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = true;
    }

    // Fill DP
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!dp[mask][u]) continue;
            if (!(mask & (1 << u))) continue; // u must be in mask

            for (int v : adj[u]) {
                if (mask & (1 << v)) continue; // v already visited
                int newMask = mask | (1 << v);
                if (!dp[newMask][v]) {
                    dp[newMask][v] = true;
                    parent[newMask][v] = u;
                }
            }
        }
    }

    // Check if any Hamilton path exists
    int fullMask = (1 << n) - 1;
    int lastVertex = -1;
    for (int i = 0; i < n; i++) {
        if (dp[fullMask][i]) {
            lastVertex = i;
            break;
        }
    }

    if (lastVertex == -1) return {}; // no Hamilton path

    // Reconstruct path
    vector<int> path;
    int mask = fullMask;
    int cur = lastVertex;
    while (cur != -1) {
        path.push_back(cur);
        int prev = parent[mask][cur];
        mask ^= (1 << cur);
        cur = prev;
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    addEdge(0,1); addEdge(1,2); addEdge(2,3); addEdge(3,4);

    vector<int> path = findHamiltonPathBitmask(n, adj);
    if (!path.empty()) {
        cout << "Hamilton path: ";
        for (int v : path) cout << v << " ";
        cout << "\n"; // 0 1 2 3 4
    } else {
        cout << "No Hamilton path exists\n";
    }
    return 0;
}

Complete C++ Implementation -- TSP (Held-Karp)

The classic Travelling Salesman Problem: find the minimum-cost Hamilton circuit.

#include <bits/stdc++.h>
using namespace std;

// Held-Karp algorithm for TSP
// dist[i][j] = distance from city i to city j (INT_MAX if no edge)
// Returns minimum cost of a Hamilton circuit starting and ending at vertex 0
// O(2^n * n^2) time, O(2^n * n) space
int tsp(int n, vector<vector<int>>& dist) {
    const int INF = 1e9;
    // dp[mask][i] = minimum cost to visit exactly the vertices in mask,
    //               starting at vertex 0 and currently at vertex i
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));

    dp[1][0] = 0; // start at vertex 0, only vertex 0 visited

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] >= INF) continue;
            if (!(mask & (1 << u))) continue;

            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue; // already visited
                if (dist[u][v] >= INF) continue; // no edge

                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v],
                                     dp[mask][u] + dist[u][v]);
            }
        }
    }

    // Close the circuit: return to vertex 0
    int fullMask = (1 << n) - 1;
    int ans = INF;
    for (int u = 1; u < n; u++) {
        if (dp[fullMask][u] < INF && dist[u][0] < INF) {
            ans = min(ans, dp[fullMask][u] + dist[u][0]);
        }
    }

    return ans;
}

int main() {
    int n = 4;
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    cout << "Minimum TSP cost: " << tsp(n, dist) << "\n"; // 80
    // Optimal tour: 0 -> 1 -> 3 -> 2 -> 0 (cost: 10+25+30+15=80)
    return 0;
}

Time Complexity: O(2^n * n^2). We have 2^n * n states, and each state considers up to n transitions.

Space Complexity: O(2^n * n) for the DP table.

Practical limit: n <= 20 (2^20 * 20^2 = ~420 million operations). For n = 23-25, careful optimization (e.g., iterating only over set bits) may still work.

Euler vs Hamilton -- Key Comparison

Aspect Euler Path/Circuit Hamilton Path/Circuit What is visited? Every EDGE exactly once Every VERTEX exactly once Existence check O(V + E) -- degree counting NP-complete -- no fast method Existence condition Undirected: 0 or 2 odd-degree Directed: in-deg = out-deg No simple condition known (Dirac/Ore: sufficient only) Finding the path O(V + E) -- Hierholzer's O(2^n * n^2) -- bitmask DP O(n!) -- backtracking Complexity class P (polynomial) NP-complete Vertex revisits? Yes, vertices can repeat No, each vertex exactly once Key algorithm Hierholzer (DFS + post-order) Held-Karp (bitmask DP) Typical constraint E up to 10^6 n up to 20 Interview frequency High (LC 332, 753, 2097) Medium (TSP, shortest superstring)

The fundamental reason for the complexity gap: Euler paths have a local characterization (vertex degrees), while Hamilton paths require global reasoning about vertex connectivity. This is one of the deepest insights in combinatorics and a favorite interview talking point.

Classic Problems with Full Solutions

Problem 1: Reconstruct Itinerary (LeetCode 332)

Problem: You are given a list of airline tickets represented as pairs [from, to]. Reconstruct the itinerary starting from "JFK" in lexicographical order. All tickets must be used exactly once.

Key insight: This is an Euler path problem on a directed multigraph. Each ticket is a directed edge. We need to find an Euler path starting from "JFK". Sorting adjacency lists gives lexicographic order.

#include <bits/stdc++.h>
using namespace std;

class Solution {
    unordered_map<string, priority_queue<string, vector<string>,
                                          greater<string>>> adj;
    vector<string> result;

    void dfs(const string& u) {
        while (!adj[u].empty()) {
            string v = adj[u].top();
            adj[u].pop();
            dfs(v);
        }
        result.push_back(u); // post-order
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& t : tickets) {
            adj[t[0]].push(t[1]);
        }
        dfs("JFK");
        reverse(result.begin(), result.end());
        return result;
    }
};

// Example:
// Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
// Output: ["JFK","MUC","LHR","SFO","SJC"]
//
// Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
// Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Why priority_queue (min-heap)? We want to visit neighbors in lexicographic order. Using a min-heap as the adjacency list ensures we always pick the smallest unused neighbor first.

Why does Hierholzer + lexicographic greedy work? By the post-order recording of Hierholzer's, "dead-end" destinations (those you visit last before backtracking) are placed at the end. The lexicographic greedy ensures we prefer the smallest option at each step, and the post-order naturally places any "detour" circuits in the correct position.

Time Complexity: O(E log E) due to sorting/heap operations.

Space Complexity: O(V + E).

Problem 2: Valid Arrangement of Pairs (LeetCode 2097)

Problem: Given a 0-indexed 2D integer array pairs where pairs[i] = [start_i, end_i], find a valid arrangement such that for every index i (except the last), end_i == start_{i+1}. Return any valid arrangement.

Key insight: Model each pair as a directed edge from start_i to end_i. A valid arrangement is an Euler path in this directed graph.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, vector<int>> adj;
        unordered_map<int, int> inDeg, outDeg;
        unordered_map<int, int> idx; // current edge pointer

        for (auto& p : pairs) {
            adj[p[0]].push_back(p[1]);
            outDeg[p[0]]++;
            inDeg[p[1]]++;
        }

        // Find start vertex for Euler path
        int start = pairs[0][0]; // default
        for (auto& [node, out] : outDeg) {
            if (out - inDeg[node] == 1) {
                start = node;
                break;
            }
        }

        // Hierholzer's algorithm
        vector<int> path;
        stack<int> stk;
        stk.push(start);

        while (!stk.empty()) {
            int u = stk.top();
            if (idx[u] < (int)adj[u].size()) {
                int v = adj[u][idx[u]++];
                stk.push(v);
            } else {
                path.push_back(u);
                stk.pop();
            }
        }

        reverse(path.begin(), path.end());

        // Convert path to pairs
        vector<vector<int>> result;
        for (int i = 0; i + 1 < (int)path.size(); i++) {
            result.push_back({path[i], path[i + 1]});
        }
        return result;
    }
};

// Example:
// Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
// Output: [[11,9],[9,4],[4,5],[5,1]]
// Euler path: 11 -> 9 -> 4 -> 5 -> 1

Note: This uses an iterative version of Hierholzer's (with an explicit stack) to avoid stack overflow for large inputs. The idx map tracks the current edge pointer for each vertex, equivalent to the recursive approach.

Time Complexity: O(E) where E = number of pairs.

Space Complexity: O(V + E).

Problem 3: Cracking the Safe (LeetCode 753)

Problem: There is a safe with a password of length n using digits 0 to k-1. Find the shortest string that contains every possible password of length n as a substring.

Key insight: This is a de Bruijn sequence problem, solvable via an Euler circuit on a de Bruijn graph.

Construction of the de Bruijn graph:

  • Each node is a string of length n-1 (there are k^(n-1) nodes).
  • Each edge represents appending a digit: node s[0..n-2] has an edge labeled d to node s[1..n-2] + d, for each digit d in 0..k-1.
  • Every node has in-degree = out-degree = k, so an Euler circuit always exists.
  • The Euler circuit visits every edge (every n-length password) exactly once.
de Bruijn Graph: n=2, k=2 (digits 0,1) Nodes = 1-char strings, Edges = 2-char passwords 0 1 00 01 10 11 Euler circuit: 0 -[00]-> 0 -[01]-> 1 -[11]-> 1 -[10]-> 0 de Bruijn sequence: "00110" Contains: 00, 01, 11, 10 (all 2-digit binary strings) 
#include <bits/stdc++.h>
using namespace std;

class Solution {
    string result;
    unordered_map<string, vector<int>> adj; // node -> list of digit edges
    unordered_map<string, int> idx;         // current edge pointer

    void dfs(const string& node) {
        while (idx[node] < (int)adj[node].size()) {
            int digit = adj[node][idx[node]++];
            string next = node.substr(1) + to_string(digit);
            dfs(next);
            result += to_string(digit); // post-order: append the edge digit
        }
    }

public:
    string crackSafe(int n, int k) {
        if (n == 1) {
            string s;
            for (int i = 0; i < k; i++) s += to_string(i);
            return s;
        }

        // Build de Bruijn graph
        // Nodes: all strings of length n-1 using digits 0..k-1
        // Edges: node s has edges labeled 0..k-1 going to s[1..]+digit
        set<string> nodes;
        function<void(string&, int)> generate = [&](string& cur, int len) {
            if ((int)cur.size() == len) {
                nodes.insert(cur);
                return;
            }
            for (int d = 0; d < k; d++) {
                cur += to_string(d);
                generate(cur, len);
                cur.pop_back();
            }
        };
        string temp;
        generate(temp, n - 1);

        for (auto& node : nodes) {
            for (int d = 0; d < k; d++) {
                adj[node].push_back(d);
            }
            idx[node] = 0;
        }

        // Start from the node "000...0" (n-1 zeros)
        string startNode(n - 1, '0');
        dfs(startNode);

        // The result is built in reverse post-order
        reverse(result.begin(), result.end());
        result = startNode + result;
        return result;
    }
};

// Example:
// n=2, k=2 -> "00110" (or "01100" etc.)
// n=1, k=2 -> "01"
// n=2, k=3 -> "0011020122" (length = 3^2 + 2 - 1 = 10)

int main() {
    Solution sol;
    cout << sol.crackSafe(2, 2) << "\n"; // "00110"
    return 0;
}

Why does this work?

Each edge in the de Bruijn graph represents a unique password of length n. An Euler circuit traverses every edge exactly once. As we traverse the circuit, we build the string by appending one digit per edge. The resulting string of length k^n + (n-1) contains every n-length password as a substring.

Time Complexity: O(k^n) -- the number of edges in the de Bruijn graph.

Space Complexity: O(k^n) for the graph and result string.

Problem 4: Shortest Superstring (LeetCode 943)

Problem: Given an array of strings words, find the shortest string that contains each string in words as a substring. Return any such string.

Key insight: This is a variant of the Travelling Salesman Problem (Hamilton path with minimum cost). We model it as: create a directed complete graph where the cost of edge (i, j) is the number of NEW characters added when appending word j after word i (accounting for overlap).

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        int n = words.size();

        // Precompute overlap: overlap[i][j] = max overlap when
        // word[i] is followed by word[j]
        vector<vector<int>> overlap(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int maxOv = min(words[i].size(), words[j].size());
                for (int k = maxOv; k >= 1; k--) {
                    if (words[i].substr(words[i].size() - k) ==
                        words[j].substr(0, k)) {
                        overlap[i][j] = k;
                        break;
                    }
                }
            }
        }

        // Bitmask DP: dp[mask][i] = max total overlap when we've used
        // the words in `mask` and the last word is words[i]
        vector<vector<int>> dp(1 << n, vector<int>(n, -1));
        vector<vector<int>> parent(1 << n, vector<int>(n, -1));

        // Base case: single words
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = 0;
        }

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if (dp[mask][last] < 0) continue;
                if (!(mask & (1 << last))) continue;

                for (int next = 0; next < n; next++) {
                    if (mask & (1 << next)) continue; // already used
                    int newMask = mask | (1 << next);
                    int newOverlap = dp[mask][last] + overlap[last][next];
                    if (newOverlap > dp[newMask][next]) {
                        dp[newMask][next] = newOverlap;
                        parent[newMask][next] = last;
                    }
                }
            }
        }

        // Find the best ending vertex
        int fullMask = (1 << n) - 1;
        int bestLast = 0;
        for (int i = 1; i < n; i++) {
            if (dp[fullMask][i] > dp[fullMask][bestLast]) {
                bestLast = i;
            }
        }

        // Reconstruct the order
        vector<int> order;
        int mask = fullMask, cur = bestLast;
        while (cur != -1) {
            order.push_back(cur);
            int prev = parent[mask][cur];
            mask ^= (1 << cur);
            cur = prev;
        }
        reverse(order.begin(), order.end());

        // Build the result string
        string result = words[order[0]];
        for (int i = 1; i < n; i++) {
            int ov = overlap[order[i - 1]][order[i]];
            result += words[order[i]].substr(ov);
        }

        return result;
    }
};

// Example:
// Input: ["alex","loves","leetcode","coding"]
// Overlap matrix:
//   alex->loves: 0, alex->leetcode: 0, alex->coding: 0
//   loves->alex: 0, loves->leetcode: 0, loves->coding: 0
//   leetcode->alex: 0, leetcode->coding: 0
//   coding->alex: 0, coding->loves: 0
//
// One optimal: "alexlovesleetcoding"
// loves->leetcode: overlap "le" = 2? No. Actually no overlap.
// leetcode->coding: overlap "codin" = no, "code" vs "codi" no...
//   "leetcode" ends with "de", "coding" starts with "co" -> no overlap
//   Actually: "leetcode" ends with "ode", "coding" starts with... no.
//   Wait: leet'cod'e vs 'cod'ing -> overlap "cod" = 3?
//   "leetcode" suffix = "code", "coding" prefix = "code"? No, "codi".
//   "leetcode"[-3:] = "ode", "coding"[:3] = "cod" -> no
//   "leetcode"[-1:] = "e", "coding"[:1] = "c" -> no
//   Actually there is no overlap, but the algorithm handles it.

int main() {
    vector<string> words = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"};
    Solution sol;
    cout << sol.shortestSuperstring(words) << "\n";
    // Output: "gctaagttcatgcatc" (length 16)
    return 0;
}

Why Hamilton path? Each word must appear exactly once as a "stop" in our tour. We want to maximize total overlap (equivalently, minimize total length). This is exactly TSP/Hamilton path with edge weights = overlap values (and we maximize).

Time Complexity: O(2^n * n^2 + n^2 * L) where L = max word length (for overlap precomputation).

Space Complexity: O(2^n * n).

Problem 5: Find Hamilton Path in a Graph

Problem: Given an undirected graph with n vertices and m edges, determine if a Hamilton path exists and output it.

This is a direct application of the bitmask DP approach. Here is the complete solution with optimizations:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (n == 1) {
        cout << "YES\n0\n";
        return 0;
    }

    // dp[mask][v] = true if there's a path visiting exactly the vertices
    // in mask, ending at v
    // Optimization: use bitset or char array instead of bool vector
    vector<vector<char>> dp(1 << n, vector<char>(n, 0));
    vector<vector<int>> parent(1 << n, vector<int>(n, -1));

    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 1;
    }

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!dp[mask][u]) continue;
            if (!(mask & (1 << u))) continue;

            for (int v : adj[u]) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                if (!dp[newMask][v]) {
                    dp[newMask][v] = 1;
                    parent[newMask][v] = u;
                }
            }
        }
    }

    int fullMask = (1 << n) - 1;
    int endVertex = -1;
    for (int i = 0; i < n; i++) {
        if (dp[fullMask][i]) {
            endVertex = i;
            break;
        }
    }

    if (endVertex == -1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        vector<int> path;
        int mask = fullMask, cur = endVertex;
        while (cur != -1) {
            path.push_back(cur);
            int prev = parent[mask][cur];
            mask ^= (1 << cur);
            cur = prev;
        }
        reverse(path.begin(), path.end());
        for (int v : path) cout << v << " ";
        cout << "\n";
    }
    return 0;
}

Time Complexity: O(2^n * n * max_degree), which is O(2^n * n * m/n) = O(2^n * m) in the worst case but effectively O(2^n * n^2) for dense graphs.

Space Complexity: O(2^n * n).

Problem 6: All Paths from Source to Target with Euler Constraint

Here is a bonus problem combining both concepts: finding an Euler path in a graph where you also need to track visited structure carefully.

Problem (variation): Given a directed graph represented by edges, find if there exists an arrangement of edges such that we can write them in sequence. This is exactly LC 2097 (Valid Arrangement of Pairs) which we covered above.

For completeness, here is an alternative iterative Hierholzer implementation that is often safer for large inputs (avoids recursion stack overflow):

#include <bits/stdc++.h>
using namespace std;

vector<int> eulerPathIterative(int n, vector<vector<int>>& adj) {
    vector<int> inDeg(n, 0);
    vector<int> idx(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u])
            inDeg[v]++;

    // Determine start vertex
    int start = -1;
    for (int i = 0; i < n; i++) {
        if ((int)adj[i].size() - inDeg[i] == 1) { start = i; break; }
    }
    if (start == -1) { // Euler circuit
        for (int i = 0; i < n; i++)
            if (!adj[i].empty()) { start = i; break; }
    }

    vector<int> path;
    stack<int> stk;
    stk.push(start);

    while (!stk.empty()) {
        int u = stk.top();
        if (idx[u] < (int)adj[u].size()) {
            stk.push(adj[u][idx[u]++]);
        } else {
            path.push_back(u);
            stk.pop();
        }
    }

    reverse(path.begin(), path.end());
    return path;
}

This iterative version is functionally identical to the recursive one but uses an explicit stack, making it suitable for graphs with millions of edges.

Common Mistakes and Interview Tips

Mistake 1: Confusing Euler and Hamilton

The most fundamental error. Euler = edges, Hamilton = vertices. If the interviewer says "visit every city exactly once," that is Hamilton. If they say "traverse every road exactly once," that is Euler. Get this wrong and the entire approach is incorrect.

Mistake 2: Forgetting Connectivity Check for Euler Paths

Having the right degree conditions is necessary but not sufficient. The graph must also be connected (or weakly connected for directed graphs). A graph with two disconnected components where all vertices have even degree does NOT have an Euler circuit.

// WRONG: only checks degrees
bool hasEulerCircuit(vector<vector<int>>& adj) {
    for (auto& neighbors : adj)
        if (neighbors.size() % 2 != 0) return false;
    return true; // BUG: doesn't check connectivity!
}

// RIGHT: checks both degrees AND connectivity
bool hasEulerCircuit(int n, vector<vector<int>>& adj) {
    // Check degrees
    for (auto& neighbors : adj)
        if (neighbors.size() % 2 != 0) return false;
    // Check connectivity (BFS/DFS from any vertex with edges)
    // ... (see full implementation above)
    return isConnected;
}

Mistake 3: Wrong Start Vertex for Euler Path

For an Euler path (not circuit), you must start at one of the two odd-degree vertices (undirected) or the vertex with out-degree - in-degree = 1 (directed). Starting at the wrong vertex will produce an incomplete path.

// WRONG: starting at vertex 0 for Euler path
dfs(0); // might fail if vertex 0 doesn't have odd degree

// RIGHT: find the correct start vertex
int start = -1;
for (int i = 0; i < n; i++) {
    if (adj[i].size() % 2 != 0) { start = i; break; }
}
if (start == -1) start = 0; // all even = Euler circuit, any start works
dfs(start);

Mistake 4: Not Handling Multi-edges in Undirected Euler

When implementing Hierholzer's for undirected graphs, forgetting to mark edges as used (not just vertices) leads to traversing the same undirected edge in both directions. You need edge IDs and a shared used array.

Mistake 5: Recursion Stack Overflow in Hierholzer's

For large graphs (E > 10^5), the recursive Hierholzer's implementation may cause stack overflow. Always have the iterative version ready.

Mistake 6: Wrong Bitmask DP State for Hamilton Path

// WRONG: checking dp[fullMask][0] only
// This finds Hamilton circuit, not path!
if (dp[fullMask][0]) ...

// RIGHT for Hamilton path: check dp[fullMask][i] for ANY i
for (int i = 0; i < n; i++)
    if (dp[fullMask][i]) { /* found */ }

// RIGHT for Hamilton circuit: check dp[fullMask][i] where edge i->0 exists
for (int i = 0; i < n; i++)
    if (dp[fullMask][i] && hasEdge(i, 0)) { /* found */ }

Mistake 7: Forgetting to Sort Adjacency List for Lexicographic Order

In LC 332 (Reconstruct Itinerary), the problem asks for the lexicographically smallest itinerary. Using a regular vector and forgetting to sort (or using a max-heap instead of min-heap) gives wrong results.

Mistake 8: Off-by-One in de Bruijn Sequence Length

The de Bruijn sequence for n-length passwords over k symbols has length k^n + (n-1), not k^n. The first n-1 characters form the initial node, and each subsequent character corresponds to one edge traversal.

Interview Tips

  1. Recognize the pattern quickly. If the problem says "use every edge/ticket/pair exactly once," think Euler. If it says "visit every node/city exactly once," think Hamilton.

  2. State the existence conditions. Before coding, tell the interviewer: "This graph has an Euler path because exactly two vertices have odd degree" or "This is NP-complete, so we need bitmask DP for n <= 20."

  3. Know the complexity contrast. Euler = O(V + E), Hamilton = O(2^n * n^2). This is a great talking point that shows deep understanding.

  4. For Euler problems, always use Hierholzer's. The DFS + post-order approach is clean, correct, and efficient. Practice writing it from memory.

  5. For Hamilton/TSP problems, check constraints. n <= 15-20 suggests bitmask DP. n <= 10 allows backtracking. n > 25 means you probably need an approximation or the problem has special structure.

  6. De Bruijn sequences come up more than you think. LC 753 is a classic, and the reduction from "shortest string containing all substrings" to Euler circuit on a de Bruijn graph is elegant and impressive in interviews.

  7. Chinese Postman is rare but shows depth. If you mention that making a non-Eulerian graph Eulerian reduces to minimum weight matching, it demonstrates strong algorithmic maturity.

Summary

EULER vs HAMILTON -- CHEAT SHEET EULER (Edges) Visits every EDGE once Existence: degree check O(V+E) Finding: Hierholzer O(V+E) Complexity class: P Key tool: DFS + post-order Typical n: up to 10^6 Problems: LC 332, 753, 2097 Related: Chinese Postman, de Bruijn sequences HAMILTON (Vertices) Visits every VERTEX once Existence: NP-complete Finding: bitmask DP O(2^n*n^2) Complexity class: NP-complete Key tool: Held-Karp bitmask DP Typical n: up to 20 Problems: TSP, LC 943 Related: shortest superstring, backtracking with pruning