Show problems as
Classic problem #797MediumBacktrackingDepth-First SearchBreadth-First SearchGraph TheoryDirected Acyclic Graph

All Paths From Source to Target

Real-world version: Parcel Routes Through the Hubs
Tracked in this browser only
Read All Paths From Source to Target on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier network runs n sorting hubs, numbered 0 through n - 1, where n is the length of links. The entry links[i] lists every hub that a parcel resting at hub i may be forwarded to. Forwarding works only in the direction listed, and the belts are laid out so that a parcel can never come back to a hub it has already left.

Parcels enter at hub 0 and leave from hub n - 1. A route is the run of hubs one parcel passes through on its way, written down in visiting order, with hub 0 first and hub n - 1 last. Two routes are different when their runs of hubs differ.

Return every route a parcel could take. The routes themselves may come back in any order, but the hubs inside each route must stay in visiting order. If nothing forwarded from hub 0 ever lands on hub n - 1, return an empty list.

Examples

Example 1

Input
links = [[2, 1], [3, 4], [3], [5], [5], []]
Output
[[0, 2, 3, 5], [0, 1, 3, 5], [0, 1, 4, 5]]

Hub 0 forwards to hub 2 and to hub 1, and each of the three answers listed runs from hub 0 to hub 5 using only forwardings named in `links`, for instance hub 0 to hub 1 to hub 4 to hub 5.

Example 2

Input
links = [[1, 2], [], [4], [4], []]
Output
[[0, 2, 4]]

Hub 1 forwards nowhere, so a parcel sent there stays put and that run of hubs is not a route. The single route ends on hub 4.

Example 3

Input
links = [[4, 2], [4], [1], [], []]
Output
[[0, 4], [0, 2, 1, 4]]

Hub 0 forwards straight to hub 4, and it also forwards to hub 2, from where a parcel reaches hub 4 by way of hub 1.

Constraints

  • n == links.length
  • 2 <= n <= 15
  • 0 <= links[i][j] < n
  • links[i][j] != i, so no hub forwards to itself
  • The entries of links[i] are distinct
  • Following the belts can never return a parcel to an earlier hub

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def hub_routes(links: list[list[int]]) -> list[list[int]]:
Java
public List<List<Integer>> hubRoutes(int[][] links)

More on the same topics