您当前的解决方案利用 回溯 。这种方法的问题在于时间复杂度成指数比例。这不好：从您输入合理数量的元素（如100多个）开始，程序就注定了失败。

鉴于您的整数列表都是（严格的）正数，一种更好的方法是使用动态 编程 。

这个想法是，如果您搜索总和 K ，那么您将定义最多 2 K + 1 个列表元素的 内存
。最初，所有存储元素（元素索引除外）均无效，在该元素中存储空集合。 __null``0

因此，最初的内存看起来像：

7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> _
1 -> _
0 -> []

if b=8（我们将b=8在此答案的其余部分中使用，但这当然仅是示例）。

有_没有（一个null指针）和[]（什么样的收集不管）一个空的集合。

现在，对于给定数字集中的每个元素，执行以下任务。您会
遍历null内存中的所有有效（而非）集合。对于每个集合，您都可以“升级”该集合：制作一个副本，将元素添加到集合中，并将其与新的和存储到索引中。如果已经有一个包含该总和的集合，则您什么也不做。这样的迭代可以实现如下：

for(int s = b-xi-1; s >= 0; s--) {
    if(cols[s+xi] == null && cols[s] != null) {
        List<int> cln = new List<int>(cols[s]);
        cln.Add(xi);
        cols[s+xi] = cln;
    }
}

与xi我们希望添加的元素。if因此，该语句检查具有sum的集合s是否有效（不是null），以及我们是否必须创建一个新集合：具有结果和的集合是否还不存在。该for环套界限：它是没有用的，升级的集合出界：这样既s+xi和s必须是有效的边界。这意味着s从0（包括）到b-xi-1（包括）的范围。我们必须向后迭代，因为否则我们可能会xi第二次添加元素。

确实，以第一个元素为例2，现在我们开始（错误地）从迭代0到8-2-1=5。现在这意味着，如果s=0，我们将“升级”空集合，因此现在的内存如下所示：

7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> [2]
1 -> _
0 -> []

（[2]是具有的集合2），是循环的下一个迭代for，s=1我们发现不存在总和为1的集合，因此我们继续进行，但是现在s=2，我们已经构造了这种集合。关键是我们的算法不做任何书签，因此
第二次加2会 导致：

7 -> _
6 -> _
5 -> _
4 -> [2,2]
3 -> _
2 -> [2]
1 -> _
0 -> []

现在，人们可以做两件事：对迭代构造了哪些集合进行书签，但这需要额外的工作，或者可以从高到低进行迭代。由于所有整数xi都保证为正，因此我们知道我们不能在downdown集合中“升级”集合。如果我们以正确的方式执行整个迭代，则内存如下所示：

7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> [2]
1 -> _
0 -> []

如果下一个元素是1，则内存如下所示：

7 -> _
6 -> _
5 -> _
4 -> _
3 -> [2,1]
2 -> [2]
1 -> [1]
0 -> []

现在给出下一个元素3，我们终于看到了动态编程的功能：

7 -> _
6 -> [2,1,3]
5 -> [2,3]
4 -> [1,3]
3 -> [2,1]
2 -> [2]
1 -> [1]
0 -> []

您会注意到我们尚未为3with
构建一个集合[3]，因为已经有这样的集合。这看起来可能并不那么令人印象深刻。但是，所有起源于此的集合[2,1]现在都不会重复，[3]如果使用
回溯 算法，情况就会如此。

在对每个元素执行此操作之后，将为每个索引的内存使用一种方式来创建具有与索引相对应的总和的子集，或者null如果无法构造此类子集。现在，您可以简单地查看构造的集合，然后选择最接近
K的 集合。我们知道，在大多数此类收集不同 ķ ，因为空收集具有总和为零，因此不同 ķ 。

可以使用以下算法讲述整个​​故事：

static List<int> GetSubset(int value, IEnumerable<int> xs) {
    int b = 2*value;
    List<int>[] cols = new List<int>[b];
    cols[0] = new List<int>();
    foreach(int xi in xs) {
        for(int s = b-xi-1; s >= 0; s--) {
            if(cols[s+xi] == null && cols[s] != null) {
                List<int> cln = new List<int>(cols[s]);
                cln.Add(xi);
                cols[s+xi] = cln;
            }
        }
    }
    for(int d = 0; d < value; d++) {
        if(cols[value-d] != null) {
            return cols[value-d];
        } else if(cols[value+d] != null) {
            return cols[value+d];
        }
    }
    return cols[0];
}

这种List<T>方法不是最有效的：您可以使用 头尾 列表方法（但不幸的是，.NET库似乎缺少这种方法）。

演示 （使用csharp交互式外壳）：

$ csharp
Mono C# Shell, type "help;" for help

Enter statements below.
csharp> public class Foo {
      >  
      > public static List<int> GetSubset(int value, IEnumerable<int> xs) {
      >         int b = 2*value;
      >         List<int>[] cols = new List<int>[b];
      >         cols[0] = new List<int>();
      >         foreach(int xi in xs) {
      >             for(int s = b-xi-1; s >= 0; s--) {
      >                 if(cols[s+xi] == null && cols[s] != null) {
      >                     List<int> cln = new List<int>(cols[s]);
      >                     cln.Add(xi);
      >                     cols[s+xi] = cln;
      >                 }
      >             }
      >         }
      >         for(int d = 0; d < value; d++) {
      >             if(cols[value-d] != null) {
      >                 return cols[value-d];
      >             } else if(cols[value+d] != null) {
      >                 return cols[value+d];
      >             }
      >         }
      >         return cols[0];
      >     }
      > }
csharp>  
csharp> int[] items = new int[] {2,3,5,7};
csharp> Foo.GetSubset(8,items);
{ 3, 5 }
csharp> Foo.GetSubset(7,items); 
{ 2, 5 }
csharp> Foo.GetSubset(9,items); 
{ 2, 7 }
csharp> Foo.GetSubset(6,items); 
{ 2, 3 }
csharp> Foo.GetSubset(10,items); 
{ 2, 3, 5 }
csharp> Foo.GetSubset(11,items); 
{ 2, 3, 5 }

如您所见6，不能用这些整数构成，但可以得出一个总计为的集合5。

这种方法的优点是您只需要搜索一次：显然可以多次调用您的方法，首先搜索值 K ，然后搜索 K + 1 ，然后搜索 K-1
，依此类推。但是问题在于，这将导致计算量大的方法。