645. Visit-Once Route
A delivery van must visit every one of n towns, numbered 0 to n - 1, exactly once. It may start in any town and finish in any town. Each pair [a, b] in edges is a two-way road between towns a and b; the van can only travel along roads, directly from one town to the next town of its tour.
Return true if such a tour exists, otherwise false. A single town is always a valid tour.
Example 1
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- true
- Explanation:
The towns lie on a line, so the tour 0 -> 1 -> 2 -> 3 visits each exactly once.
Example 2
- Input:
- n = 4, edges = [[0,1],[0,2],[0,3]]
- Output:
- false
- Explanation:
Town 0 is the centre of a star. Any tour would have to pass through town 0 twice to reach all three leaves, so none exists.
Example 3
- Input:
- n = 1, edges = []
- Output:
- true
- Explanation:
With one town the van is already done.
Constraints
- 1 ≤
n≤ 12 - 0 ≤
edges.length≤ 66 0 ≤ a, b < n; roads may be listed more than once, and a road from a town to itself is ignored.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(2^n * n^2)
- Space
- O(2^n)