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;
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 < 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 < subSetIndexes.Length; i++)
{
Console.Write(set[subSetIndexes[i]]);
if (i < 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 < arr.Length; i++)
{
Console.Write(arr[i]);
if (i < arr.Length - 1)
{
Console.Write(" ,");
}
}
Console.WriteLine("}");
}