14,973,838 members
Articles / Programming Languages / C#
Alternative
Tip/Trick
Posted 17 Apr 2014

8.4K views
7 bookmarked

# Subset - Sum Problem with Numeric Collections

Rate me:
This is an alternative for "Subset - Sum Problem with Integer Arrays "

## Introduction

Here, I am going to solve the Subset-sum problem using an indexable collection. We have to find a set of values where its sum is equal to or greater than some other value.

In this alternative, I've implemented a generic method to generate all of the combinations' indexes for a collection. (i.e., all of the sets of indexes corresponding to all of the combinations of elements.) With that, the extension to non-Integer collections is possible.

For example: Assume there is an integer array `int[] values = { 1, 2, 4, 6 }; `our problem is to find all the subsets where the sum of the indexed values is `>= 10`, and set of index's should be unique.

The result should be:

1. 0,2,3
2. 1,2,3
3. 2,3
4. 0,1,2,3

## Using the Code

This is the complete implementation as a simple console application.

First, I calculate how many combinations there are for the collection. Then I iterate through that many combinations, using the current counter (`bits`) to generate the set of indexes corresponding to that combination. Since each index is represented by a bit in the `bits` value, all possible combinations will be generated.

C#
```using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication31
{
class Program
{
static void Main(string[] args)
{
int[] test = new int[] { 1, 2, 4, 6 };
int threshold = 10;
foreach (var item in CombinationIndexes(test).Where(ii => ii.Sum(ix => test[ix]) >= threshold))
{
Console.WriteLine(string.Join(",", item.Select(i => i.ToString())));
}
}

const int BitsInUlong = 8 * sizeof(ulong);
static IEnumerable<IEnumerable<int>> CombinationIndexes<T>(IList<T> collection)
{
if (collection.Count > BitsInUlong)
throw new ArgumentOutOfRangeException("collection", "collection is too large");
ulong count = (~(ulong)0) >> (BitsInUlong - collection.Count);
for (ulong bits = 0; bits <= count; bits++)
{
yield return BitNumbers(bits);
}
}

static IEnumerable<int> BitNumbers(ulong bits)
{
if (bits == 0)
yield break;
for (int i = 0; i < BitsInUlong; ++i)
{
if ((bits & mask) != 0)
{
yield return i;
}
}
}
}
}```

## Points of Interest

I use a `ulong` to represent the indexable positions into the collection while generating the combinations, so the largest collection supported is 64 elements. However, there are 18,446,744,073,709,551,615 combinations of 64 elements, so the restriction isn't that significant!

I could have used `BigInteger` to remove the restriction on number of elements. That is left as an exercise for the reader.

## History

• First version of the alternative