C#用DFS求树路径和时嵌套List<T>引用丢失问题如何解决

你遇到的问题本质是引用类型传递导致的内容异常：

• C#中List<T>属于引用类型，你整个DFS递归过程中全程复用同一个list实例存储当前路径
• 执行results.Add(list)时，只是将该list实例的内存引用添加到结果集，并没有拷贝路径内容
• 后续回溯阶段执行list.RemoveAt(list.Count - 1)会直接修改该实例的内容，递归全部结束后该list会被清空，结果集中所有引用指向的都是同一个空列表，就会出现「内部List引用丢失」的表象。

只需要修改添加结果的逻辑，存入结果集时创建当前路径的深拷贝即可：
将results.Add(list)修改为results.Add(new List<T>(list))，用当前路径的元素创建一个新的List<T>实例存入结果集，后续原list的修改就不会影响已经保存的结果。

private void DfsPathGivenSum(Tree<T> node, List<T> list, int sum, List<List<T>> results)
{
    list.Add(node.Key);

    foreach (var child in node.children)
    {
        this.DfsPathGivenSum(child, list, sum, results);
    }

    var currentPathSum = list.Sum(x => int.Parse(x.ToString()));
    if (currentPathSum == sum)
    {
        // 改为添加路径副本，而非原引用
        results.Add(new List<T>(list));
    }

    list.RemoveAt(list.Count - 1);
}

可以在递归过程中维护当前路径的和，而不是每次都调用Sum遍历计算，降低时间复杂度：每次Add节点时累加和，Remove节点时扣减和，判断条件直接使用维护的动态和即可。

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