Sum of Array's Subsets

Question

Im looking for some help with finding subsets of array.

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

I have to find all subsets of an array. If sum of the subsets elements equal to any number in array then my counter increment. 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 ok with 2-elements and 3-elements of subsets. But 4 and above I can't figured out how to solve it?

Any help would be greatly appreciated

Answer 1

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

With the first index as starting points the subsets are 1+2, 1+2+3, 1+2+3+5 and so on. As you are only interested in the sum of the subsets you can just add one item after the other to get the sum of the subsets.

Then for each sum loop through the items to check for a match:

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:

I assumed that you meant continuous subsets, but from your examples it seems that you also want non-continuous subsets.

Lets's start with the correct solution:

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

That gives us 14 different subsets that sums up to an item in the set.

You can count the subsets recursively, only keeping track of the sum and number of items in subsets. You don't need the actual subsets, only to know the sum and that there are at least two items in the subset.

The subsets in a set is the first item combined with all subsets in the rest of the set, plus the subsets in the rest of the set. For example the subsets s() of [1,2,3] is 1,s([2,3]) and s([2,3]).

This gives you:

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

And calling it:

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

Output:

14

Answer 2

This seems a lot like homework to me. So I will answer in that spirit (i.e. rather than write the code, point you in the right direction).

First, it's not really clear what you mean by "subset". Are you talking about contiguous runs of elements from the array? Or do you literally mean treating the array as an unordered set, from which you examine every possible subset?

The latter is significantly harder than the former. So I'm going to assume the former for the moment.

Then, it seems you really have two different problems:

• Find all subsets of the array and sum each one
• For a given sum, determine whether it's in the array

The latter is fairly straightforward. If you know these arrays will always be relatively short (and hopefully they will be, otherwise "find all subsets" may take awhile :) ), you can just do a linear search every time you have a new sum to look for.

Alternatively, a more semantically straightforward approach would be to create a HashSet<int> instance once using the members of the array, and then when you want to know if the sum is in the array, just check your set.

For example:

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

Then you can just write setOfValues.Contains(sum) to check whether the value held by the variable sum is contained in the array.

As for the first problem, it seems to me that you really should only need two loops:

• A loop to iterate on the index of the first element of a subset. I.e. you need to enumerate all subsets, first starting with all subsets that start with element 0, then with all subsets that start with element 1, and so on.
• A loop to iterate on the length of the subset. I.e. having determined the starting index for your current group of subsets, now you want to find all the actual subsets: the first has length 1, the second has length 2, and so on up to the maximum possible length (i.e. the length of the array minus the current 0-based starting index value).

Considering for a moment the alternative possibility — that you are treating the array as an unordered set — then it seems to me an obvious, if brute-force approach, would be to generate the subsets recursively.

In that approach, you would again have a loop to enumerate the subset lengths, starting with 1, up to the total length of the original set. Then, given a length, you need to pick all possible subsets.

You can do this recursively:

• Given a set, iterate over the elements of the current set (passed in to your recursive method). The current element is the new element of your current subset.
• If your current subset is now the correct length, sum it and compare to the original set.
• Otherwise, remove the current element from the current set and recurse.

The easiest implementation of the above will create new copies of the current set for each level of recursion, to pass to the method when it calls itself. This way you don't have to worry about one level of recursion interfering with previous levels.

Do note that this is going to be practical only for relatively small initial sets. It won't take very large initial arrays before your computer doesn't have enough time or memory to complete the search of all possible subsets.

Answer 3

First up, you need a method that will return all subsets.

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

So given getAllSubsets(new[] { 1, 2, 3 }) I get:

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

Now's it's easy to compute the result you want.

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

var result =
    getAllSubsets(array)
        .Where(ss => array.Contains(ss.Sum()))
        .Count();

I get 22.

Answer 4

Using a bit of 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);

Gives you:

Number of subsets:5