Subset - Sum Problem with Numeric Collections

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.

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())));
      }
      Console.ReadLine();
    }
 
    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;
      ulong mask = 1;
      for (int i = 0; i < BitsInUlong; ++i)
      {
        if ((bits & mask) != 0)
        {
          yield return i;
        }
        mask <<= 1;
      }
    }
  }
}

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