求助：通过递归生成从起始ID到目标ID的所有有效路径

我懂你的痛点——当前的递归代码只揪出了一条从1到3的路径，但实际上明明有两条合法路径：(1,2,3)和(1,5,3)。问题大概率出在你的函数找到一条路径后就直接终止了，没做回溯去探索其他分支。

先把你的邻接表转成代码里好用的结构（比如Python字典）：

adjacency_table = {
    1: [2, 5],
    2: [1, 3, 4, 5],
    3: [2, 5],
    4: [2],
    5: [1, 2, 3]
}

下面是修复后的回溯式递归函数，能找出所有符合要求的路径：

def find_all_paths(adj, start, end):
    all_paths = []
    
    def backtrack(current_node, current_path, visited):
        # 把当前节点加入路径和已访问集合
        current_path.append(current_node)
        visited.add(current_node)
        
        # 到达目标节点，保存路径副本（必须存副本，否则后续回溯会修改它）
        if current_node == end:
            all_paths.append(current_path.copy())
        else:
            # 遍历所有邻接节点，跳过已经访问过的
            for neighbor in adj[current_node]:
                if neighbor not in visited:
                    backtrack(neighbor, current_path, visited)
        
        # 关键的回溯步骤：移除当前节点，让其他分支能重新探索这条路径
        current_path.pop()
        visited.remove(current_node)
    
    # 初始调用：从起始节点开始，空路径，空访问集合
    backtrack(start, [], set())
    return all_paths

# 测试一下
paths = find_all_paths(adjacency_table, 1, 3)
print(paths)  # 输出: [[1, 2, 3], [1, 5, 3]]

核心要点解释： #

• 回溯机制：每次递归完成后，把当前节点从路径和访问集合中移除，这样函数就能回到上一个节点，去尝试其他未探索的邻接节点（比如找到1→2→3后，回溯到2、再回溯到1，接着去探索1→5→3这条分支）
• 避免重复节点：用visited集合记录已经走过的节点，防止路径出现循环（比如1→2→1→3这种无效路径）
• 保存路径副本：因为current_path是列表，是可变对象，如果直接存引用，后续回溯修改会导致结果里的路径都变成最后修改后的样子，所以必须存copy()

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