Subset sum problem implementation

Here is a recursive implementation of the Subset sum problem:

```
using System;

namespace Exercise
{
class SubsetSum
{
static void Main(string[] args)
{
set = new int[] { 2, 3, 1, -1};
PrintSet(set, "Initial Set.");

sum = 4;
Console.WriteLine("Wanted sum = {0}", sum);

FindSubsetSum();
}
//-------------------------------------------------------------

static int[] set;
static int[] subSetIndexes;
static int sum;
static int numberOfSubsetSums;

//------------------------------------------------------------

/*
Method: FindSubsetSum()
*/
private static void FindSubsetSum()
{
numberOfSubsetSums = 0;
int numberOfElements = set.Length;
FindPowerSet(numberOfElements);
}
//-------------------------------------------------------------

/*
Method: FindPowerSet(int n, int k)

*/
private static void FindPowerSet(int n)
{
// Super set - all sets with size: 0, 1, ..., n - 1
for (int k = 0; k <= n - 1; k++)
{
subSetIndexes = new int[k];
CombinationsNoRepetition(k, 0, n - 1);
}

if (numberOfSubsetSums == 0)
{
Console.WriteLine("No subsets with wanted sum exist.");
}
}
//-------------------------------------------------------------

/*
Method: CombinationsNoRepetition(int k, int iBegin, int iEnd);

*/
private static void CombinationsNoRepetition(int k, int iBegin, int iEnd)
{
if (k == 0)
{
PrintSubSet();
return;
}

for (int i = iBegin; i <= iEnd; i++)
{
subSetIndexes[k - 1] = i;
++iBegin;
Combina

My major critique of your code is that you mix up all kinds of concerns all over the place. The code that computes the subsets also does the printing and the counting and all that stuff.

Some thoughts on how to improve this:

-
The problem is the subset sum problem. Its input is a set of integers. So why do you do everything in arrays? Make a class Set, or use an existing class, and have that represent your set of integers.

-
Once you have that class, build basic operations out of it. So for example, a Set should have a PowerSet member, which returns Set>, or even better, EnumeratePowerSet, which returns IEnumerable>.

-
Now that you have those operations, you can use LINQ to do queries against them.

In short, I'd like to see a method like this:

// Takes a set and a sum, returns a sequence of subsets that 
// sum to the given value.
static IEnumerable> SubsetSum(Set items, int sum)
{
  return from subset in items.EnumeratePowerSet()
         where subset.Sum() == sum
         select subset;
}
static void Display(IEnumerable> subsets)
{
  if (!subsets.Any())
    Console.WriteLine("No subsets sum to that value.");
  else
    foreach(var subset in subsets)
      PrintSubset(subset);

Now, can you implement the EnumeratePowerSet method on Set?


Is the complexity of this algorithm 2n, where n - number of elements in the array?

Yes.


Is there more efficient approach to that problem, probably iteration instead of recursion?

There is no known algorithm that does better than exponential in general. (There is no proof that there is no such algorithm. The discovery of such an algorithm or a proof that none exists would be a major result in computer science.)

However there are algorithms that do better on typical subset sum problems given certain constraints. There is a huge amount of research on this problem; I leave it to you to consult your local university library.

StackExchange Code Review Q#144172, answer score: 5