Sum of array subsets

Question

I need help finding subsets of an array.

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

I need to find all subsets of an array. If the sum of the elements of the subsets is equal to any number in the array, then my counter is incremented. For example: 1 + 2 = 3, 2 + 3 = 5, 5 + 8 + 10 = 23, 1 + 2 + 5 = 8, 2 + 3 + 8 + 10 = 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();
    }

I'm fine with 2-elements and 3-elements of subsets. But 4 and above, I can’t figure out how to solve it?

Any help would be greatly appreciated.

Answer 1

You only need two loops to find the sum of all the subsets. The outer loop is the starting point of the subsets, and the inner loop calculates the sum of all the subsets from this starting point.

1+2, 1+2+3, 1+2+3+5 . , , .

, :

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);

Edit:

, , , .

:

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 , .

, . , .

- , , . , s() of [1,2,3] 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

Answer 2

, . ( , ).

-, , "". ? , ?

. .

, , :

• ,

. , (, , , " " :)), , .

HashSet<int> , , , , .

:

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

setOfValues.Contains(sum), , , sum.

, , :

• . , , 0, , 1 ..
• . , : 1, 2 (.. 0).

; — , , .

, 1, . , , .

:

• , ( ). - .
• , .
• recurse.

, . , , .

, . , .

Answer 3

, , .

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.

Answer 4

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