数组'5个子集的和

int[] array = { 1,2,3,5,8,10,15,23};

public static void Main(string[] args)
    {
        int[] array = { 1, 2, 3, 5, 8, 10, 15, 23 };
        int arrayLength = array.Count();
        int sum = 0;
        int subsetCount = 0;
        for (int i = 0; i < arrayLength; i++)
        {
            for (int j = i + 1; j < arrayLength; j++)
            {
                sum = array[i] + array[j];
                for (int m = j + 1; m < arrayLength; m++)
                {
                    for (int k = 0; k < arrayLength; k++)
                    {
                        if (array[k] == sum)
                        {
                            subsetCount++;
                        }
                    }
                    sum = array[i] + array[j] + array[m];
                }
            }
        }
        Console.WriteLine(subsetCount);
        Console.ReadLine();
    }

你只需要两个循环找到所有子集的和。外部循环是子集的起始点，内部循环从该起始点计算所有子集的和。

以第一个索引为起点，子集为1+2、1+2+3、1+2+3+5等。由于您只对子集的和感兴趣，因此您可以将一项接着另一项相加以得到子集的和。

然后对每个sum循环遍历项以检查是否匹配:

int[] array = { 1, 2, 3, 5, 8, 10, 15, 23 };
int subsetCount = 0;
for (int i = 0; i < array.Length; i++) {
  int sum = array[i];
  for (int j = i + 1; j < array.Length; j++) {
    sum += array[j];
    for (int k = 0; k < array.Length; k++) {
      if (array[k] == sum) {
        subsetCount++;
      }
    }
  }
}
Console.WriteLine(subsetCount);

编辑:

我以为你是指连续的子集，但从你的例子来看，你似乎也想要非连续的子集。

让我们从正确的解决方案开始:

23 = 15+8, 15+5+3, 15+5+2+1, 10+8+5, 10+8+3+2
15 = 10+5, 10+3+2, 8+5+2
10 = 8+2, 5+3+2
 8 = 5+3, 5+2+1
 5 = 3+2
 3 = 2+1

这给了我们14个不同的子集，它们加起来就是集合中的一个项。

您可以递归地计数子集，只跟踪子集中项目的总和和数量。您不需要实际的子集，只需要知道和，并且子集中至少有两个项。

集合中的子集是第一个元素与该集合其余部分中的所有子集的组合，加上该集合其余部分中的子集。例如[1,2,3]的子集s()是1,s([2,3])和s([2,3])。

这给你:

public static int CountSubsets(int[] arr, int start, int len, int sum) {
  int cnt = 0;
  if (start < arr.Length) {
    if (len >= 1 && arr.Contains(sum + arr[start])) cnt++;
    cnt += CountSubsets(arr, start + 1, len + 1, sum + arr[start]);
    cnt += CountSubsets(arr, start + 1, len, sum);
  }
  return cnt;
}

调用它:

int[] set = { 1, 2, 3, 5, 8, 10, 15, 23 };
Console.WriteLine(CountSubsets(set, 0, 0, 0));

输出:

14

这对我来说很像家庭作业。因此，我将本着这种精神回答(即，与其编写代码，不如为您指出正确的方向)。

首先，你所说的"子集"是什么意思并不清楚。你说的是数组中元素的连续运行吗?或者你的意思是把数组当作一个无序的集合，从中检查每一个可能的子集?

后者明显比前者更难。所以我现在假设是前者。

那么，你似乎真的有两个不同的问题:

• 查找数组的所有子集并对每个子集求和
• 对于给定的和，确定它是否在数组
中

后者相当简单。如果你知道这些数组总是相对较短(希望如此，否则"找到所有子集"可能需要一段时间:))，你可以在每次有新的和要查找时进行线性搜索。

或者，一种语义上更直接的方法是使用数组的成员创建一个HashSet<int>实例，然后当您想知道该和是否在数组中时，只需检查您的集合。

例如:

HashSet<int> setOfValues = new HashSet<int>(array);

那么你可以直接写setOfValues.Contains(sum)来检查变量sum保存的值是否包含在数组中。

对于第一个问题，在我看来，你真的应该只需要两个循环:

• 对子集的第一个元素的索引进行迭代的循环。例如，您需要枚举所有子集，首先从所有以元素0开始的子集开始，然后从所有以元素1开始的子集开始，依此类推。
• 对子集长度进行迭代的循环。也就是说，已经确定了当前子集组的起始索引，现在你想找到所有实际的子集:第一个长度为1，第二个长度为2，以此类推，直到最大可能的长度(即数组的长度减去当前以0为基础的起始索引值)。

考虑一下另一种可能性—你将数组视为一个无序的集合—那么在我看来，一个明显的，如果是蛮力的方法，将是递归地生成子集。

在这种方法中，您将再次有一个循环来枚举子集长度，从1开始，直到原始集合的总长度。然后，给定一个长度，你需要选择所有可能的子集。

你可以递归地这样做:

• 给定一个集合，遍历当前集合的元素(传递给递归方法)。当前元素是当前子集的新元素。
• 如果当前子集的长度是正确的，将其相加并与原始集合进行比较。
• 否则，从当前集合中删除当前元素并递归。

上面最简单的实现是为每一级递归创建当前集合的新副本，以便在方法调用自己时传递给方法。这样，你就不必担心一层递归会干扰前一层。

请注意，这只适用于相对较小的初始集合。在您的计算机没有足够的时间或内存来完成所有可能子集的搜索之前，它不会占用非常大的初始数组。

首先，您需要一个返回所有子集的方法。

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null;
getAllSubsets = xs =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        :  xs.Skip(1).Any()
            ? getAllSubsets(xs.Skip(1))
                .SelectMany(ys => new [] { ys, xs.Take(1).Concat(ys) })
            : new [] { Enumerable.Empty<int>(), xs.Take(1) };

给定getAllSubsets(new[] { 1, 2, 3 })，我得到:

{  } 
{ 1 } 
{ 2 } 
{ 1, 2 } 
{ 3 } 
{ 1, 3 } 
{ 2, 3 } 
{ 1, 2, 3 } 

现在很容易计算出你想要的结果。

int[] array = { 1,2,3,5,8,10,15,23};
var result =
    getAllSubsets(array)
        .Where(ss => array.Contains(ss.Sum()))
        .Count();

我得到22

使用一点Linq:

int[] array = {1, 2, 3, 5, 8, 10, 15, 23};
var subsets = new List<IEnumerable<int>>();
int counter = 0;
for (int i = 0; i < array.Length; i++)
{
    for (int j = 2; j < array.Length - i; j++)
    {
        if (array.Contains(array.Skip(i).Take(j).ToList().Sum()))
        {
            counter++;
        }
    }
}
Console.WriteLine("Number of subsets:" + counter);

给你:

子集数:5