Hamiltonian Path Exists
01 · Problem
You are given an undirected graph with n vertices labeled 1 to n and a list edges, where edges[i] = [u, v] connects vertices u and v.
A Hamiltonian path is a sequence of vertices that visits every vertex exactly once, where each pair of consecutive vertices is joined by an edge. The path may start and end at any vertices; it does not need to return to its start.
Return true if the graph contains a Hamiltonian path, and false otherwise. A graph with a single vertex trivially has one.
02 · Examples
n = 4, edges = [[1,2],[2,3],[3,4],[2,4]]
true
The path 1 -> 2 -> 3 -> 4 uses only existing edges and visits every vertex once.
n = 4, edges = [[1,2],[1,3],[1,4]]
false
This is a star centered at 1. Any path can pass through 1 only once, so it can reach at most two of the leaves 2, 3 and 4.
n = 1, edges = []
true
A single vertex on its own is a path that visits every vertex.
03 · Constraints
- 01`1 <= n <= 10`
- 02`0 <= edges.length <= n * (n - 1) / 2`
- 03`edges[i].length == 2`, `1 <= u, v <= n`, `u != v`
- 04There are no duplicate edges
04 · Optimal complexity
- Time
- O(2^n * n^2)
- Space
- O(2^n * n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.