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 &lt;= 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 &lt;= iEnd; i++)
            {
                subSetIndexes[k - 1] = i;
                ++iBegin;
                CombinationsNoRepetition(k - 1, iBegin, iEnd);
            }
        }

    }
}


Input:  


  -


Output: 


  Initial Set.
   {2 ,3 ,1 ,-1}
   Wanted sum = 4
   (1 ,3)
   (-1 ,3 ,2)


The algorithm is based on finding the Power setexcept the trivial empty set of indexes, which is in turn based on finding all the combinationswithout repetition of indexes with size 1, 2,..., n. Then the sets of indexes corresponding to array elements with the wanted sum are printed. 

Any comments regarding the style and implementation will be appreciated.

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

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



Here are the helper functions:

    private static void PrintSubSet()
    {
        int currentSubsetSum = 0;

        // accumulate sum of current subset
        for (int i = 0; i &lt; subSetIndexes.Length; i++)
        {
            currentSubsetSum += set[subSetIndexes[i]];
        }

        // if wanted sum: print current subset elements
        if (currentSubsetSum == sum)
        {
            ++numberOfSubsetSums;

            Console.Write("(");
            for (int i = 0; i &lt; subSetIndexes.Length; i++)
            {
                Console.Write(set[subSetIndexes[i]]);

                if (i &lt; subSetIndexes.Length - 1)
                {
                    Console.Write(" ,");
                }
            }
            Console.WriteLine(")");
        }
    }
    //-------------------------------------------------------------

    private static void PrintSet(int[] arr, string label = "")
    {
        Console.WriteLine(label);

        Console.Write("{");
        for (int i = 0; i &lt; arr.Length; i++)
        {
            Console.Write(arr[i]);

            if (i &lt; arr.Length - 1)
            {
                Console.Write(" ,");
            }
        }
        Console.WriteLine("}");
    }
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&lt;T&gt; should have a PowerSet member, which returns Set&lt;Set&lt;T&gt;&gt;, or even better, EnumeratePowerSet, which returns IEnumerable&lt;Set&lt;T&gt;&gt;.  
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&lt;Set&lt;int&gt;&gt; SubsetSum(Set&lt;int&gt; items, int sum)
{
  return from subset in items.EnumeratePowerSet()
         where subset.Sum() == sum
         select subset;
}
static void Display(IEnumerable&lt;Set&lt;int&gt;&gt; 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&lt;T&gt;?


  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.