Attraction Route Without Reusing Trails

An attraction park is an undirected graph. Vertices are locations and each trail is an undirected edge that may be traversed at most once.
Find a route that starts at start, ends at end, and visits every vertex in desiredAttractions at least once. Other vertices may be visited, and vertices may repeat when reached through different unused trails.
Return the lexicographically smallest valid vertex sequence. Compare two routes at their first differing vertex, and prefer the shorter route when one is a prefix of the other. Return an empty array when no valid route exists.

Function
findAttractionRoute(n: int, trails: int[][], desiredAttractions: int[], start: int, end: int) → int[]

Examples
Example 1
n = 5
trails = [[0,1],[1,2],[2,4],[1,3],[3,4],[1,4]]
desiredAttractions = [2,3]
start = 0
end = 4
return = [0,1,2,4,1,3,4]
The route uses each listed trail at most once and visits both requested attractions. It is lexicographically smaller than alternatives beginning 0,1,3.
Example 2
n = 4
trails = [[0,1],[1,2],[2,3]]
desiredAttractions = [1,2]
start = 0
end = 3
return = [0,1,2,3]
The only start-to-end route visits both desired vertices.
Example 3
n = 4
trails = [[0,1],[2,3]]
desiredAttractions = [2]
start = 0
end = 3
return = []
The graph components are disconnected.

Constraints
1 <= n <= 12.
0 <= trails.length <= 18.
Each trail contains two distinct vertices in [0, n - 1]; parallel trails are allowed and are distinct edges.
desiredAttractions.length <= n.
start, end, and every desired attraction are valid vertices.

With 18 edges, brute force over edge usage is feasible, so this is backtracking with a bitmask of used edges. Run DFS from start. At each vertex, try neighbors in increasing vertex order, mark the edge used, and recurse. Track which desired attractions have been visited, also as a bitmask. When you stand on end with all attractions covered, you have a candidate. Because you explore smallest neighbor first, the first valid complete route is smallest, except for the prefix rule: stopping at end beats continuing, so check for completion before extending. Pitfalls: parallel edges are distinct, so index them by edge id, not by neighbor. Passing through end mid-route is legal. Memoize on (vertex, usedEdgeMask, visitedMask) to prune dead states, since 12 x 2^18 x 2^12 is only worth caching on failures. StealthCoder is your hedge if the pruning logic slips live.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.