JavaScript实现数组追尾式无重复拼接生成目标路径的问题

这道题本质是有向图的全路径遍历，输入的每个二元组[u, v]对应一条u指向v的有向边，要求输出所有从起点0出发、到出度为0的节点结束的完整路径。

• 先构建邻接表存储图结构：遍历所有输入二元组，以每个元素的第一个值为键，第二个值存入对应键的列表中，后续可以O(1)查询任意节点的所有后继节点。
• 用深度优先搜索（DFS）回溯遍历所有路径：从起点0出发，维护当前遍历的路径，每访问一个后继节点就加入路径，直到当前节点没有后继节点时，将当前路径存入结果集，再回溯走其他分支。

# 输入数据
input_arr = [
  [ 0, 1 ],   [ 0, 2 ],   [ 0, 3 ],
  [ 0, 4 ],   [ 1, 5 ],   [ 2, 6 ],
  [ 3, 7 ],   [ 4, 10 ],  [ 4, 11 ],
  [ 4, 12 ],  [ 4, 13 ],  [ 5, 29 ],
  [ 6, 29 ],  [ 7, 8 ],   [ 8, 29 ],
  [ 9, 29 ],  [ 12, 18 ], [ 13, 19 ],
  [ 17, 29 ], [ 18, 29 ], [ 19, 29 ],
  [ 21, 29 ], [ 24, 29 ], [ 26, 29 ],
  [ 28, 29 ]
]
# 构建邻接表
adj = {}
for u, v in input_arr:
    if u not in adj:
        adj[u] = []
    adj[u].append(v)
result = []
# DFS回溯遍历
def dfs(current_node, current_path):
    # 当前节点没有后继，路径终止，加入结果
    if current_node not in adj:
        result.append(current_path.copy())
        return
    # 遍历所有后继节点
    for next_node in adj[current_node]:
        current_path.append(next_node)
        dfs(next_node, current_path)
        # 回溯，移除刚加入的节点，走其他分支
        current_path.pop()
# 初始调用，起点为0，初始路径为[0]
dfs(0, [0])
# 打印结果
print(result)

运行上述代码得到的结果和你给出的目标输出完全一致：

[[0, 1, 5, 29], [0, 2, 6, 29], [0, 3, 7, 8, 29], [0, 4, 10], [0, 4, 11], [0, 4, 12, 18, 29], [0, 4, 13, 19, 29]]

内容的提问来源于stack exchange，提问作者devdev