回溯法实现组合问题：返回列表元素为空的原因分析

我正在学习回溯法，遇到如下问题：给定两个整数n和k，返回从范围[1, n]中选取k个数的所有可能组合，返回顺序不限。用n=4、k=2测试时，编写的C#代码返回的list包含6个元素（数量正确），但每个元素都是空集合。调试时能找到正确组合，但最终返回的列表元素为空。

相关代码如下：

IList<IList<int>> Combine(int n, int k)
{
    IList<IList<int>> list = new List<IList<int>>();
    IList<int> listComb = new List<int>();
    backtrack(1, n, k, list, listComb);

    return list;
}
void backtrack(int start,int end,int k,IList<IList<int>> list,IList<int> oneComb)
{
    if (oneComb.Count == k)
    {
        list.Add(oneComb);
        return;
    }

    for(int i= start; i <= end; i++)
    {
        oneComb.Add(i);
        backtrack(i + 1, end, k, list, oneComb);
        oneComb.RemoveAt(oneComb.Count-1);
    }
}

Combine(4, 2);

调试时可看到正确组合（截图如下）：

问题根源 #

你在回溯过程中始终复用同一个oneComb集合对象。当执行list.Add(oneComb)时，只是将该集合的引用添加到结果列表中，而非创建一个独立的副本。后续的RemoveAt操作会修改这个共享的集合，最终所有引用指向的都是被清空后的集合，因此返回的结果全是空集合。

修复方案 #

当满足oneComb.Count == k的条件时，添加集合的副本到结果列表，这样后续的回溯操作不会影响已保存的组合。修改backtrack方法中的判断逻辑即可：

if (oneComb.Count == k)
{
    list.Add(new List<int>(oneComb)); // 创建副本添加
    return;
}

修改后的完整代码 #

IList<IList<int>> Combine(int n, int k)
{
    IList<IList<int>> list = new List<IList<int>>();
    IList<int> listComb = new List<int>();
    backtrack(1, n, k, list, listComb);

    return list;
}
void backtrack(int start,int end,int k,IList<IList<int>> list,IList<int> oneComb)
{
    if (oneComb.Count == k)
    {
        list.Add(new List<int>(oneComb));
        return;
    }

    for(int i= start; i <= end; i++)
    {
        oneComb.Add(i);
        backtrack(i + 1, end, k, list, oneComb);
        oneComb.RemoveAt(oneComb.Count-1);
    }
}

这样修改后，返回的结果列表中会包含6个正确的非空组合：[1,2]、[1,3]、[1,4]、[2,3]、[2,4]、[3,4]。

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