C#:
class RecursiveSubsetSumEfficient {
/// <summary>
/// program that finds all subsets of numbers in the array, which have a sum N. For example,
/// if we have the array {2, 3, 1, -1} and N=4, we can obtain N=4 as a sum in the following two ways: 4 = 2+3-1; 4 = 3+1.
/// </summary>
static int numberOfElements = 0, numberOfSubsets = 1, sumOfNumberToFind = 0, count = 0, sum = 0;
static int[] subsets, inputValues;
static void GenerateSubsetWithSum(int currentLoop, int currentLoopValue, int boundary)
{
//here we generate combinations for 1,2..N number of elements
while (numberOfSubsets <= numberOfElements)
{
subsets = new int[numberOfSubsets];
GenerateSubsets(currentLoop, currentLoopValue, numberOfSubsets);
numberOfSubsets++;
}
}
static void GenerateSubsets(int currentLoop, int currentLoopValue, int boundary)
{
if (currentLoop == numberOfSubsets)
{
if ((sum + (inputValues[subsets[currentLoop - 1]])) == sumOfNumberToFind)
{
printSubsetsWithSum();
}
return;
}
//ensures that all elements prior to the last element in the array is calculated just once and used
//through out until its no longer needed.
if (currentLoop != 0 && currentLoop == (numberOfSubsets - 1))
{
if(sum == 0)
{
sum = checkSumOfNumbers();
}
else
{
sum += inputValues[subset[currentLoop - 1]];
}
}
for (int i = currentLoopValue; i <= (numberOfElements - boundary); i++)
{
subsets[currentLoop] = i;
GenerateSubsets(currentLoop + 1, i + 1, boundary - 1);
}
if (currentLoop != 0)
{
sum = sum - inputValues[subsets[currentLoop - 1]];
}
}
static void printSubsetsWithSum()
{
count++;
Console.WriteLine("count so far {0}", count);
for (int i = 0; i < subsets.Length; i++)
{
if (i == 0)
{
Console.Write("{0}", inputValues[subsets[i]]);
}
else
{
Console.Write(" + {0}", inputValues[subsets[i]]);
}
}
Console.Write(" = {0}", sumOfNumberToFind);
Console.WriteLine();
}
static int checkSumOfNumbers()
{
int total = 0, value = 0;
//check to see if we have a sum of the Number N.
for (int j = 0; j < subsets.Length - 1; j++)
{
value = subsets[j];
total += inputValues[value];
}
return total;
}
static void Main(string[] args)
{
inputValues = new int[] {2,3,1,10,17,39,20,41,67,109,46,56,92,110,38,97,42,32,42,63,51,23,54,96,88,18,23,82,51};
sumOfNumberToFind = 165;
numberOfElements = inputValues.Length;
GenerateSubsetWithSum(0, 0, numberOfSubsets);
Console.WriteLine("finshed on time");
Console.ReadLine();
}
}
numberOfSubsets is simply the possible n combination of numbers(in this instance n is 4) that add up to 165. i chose 165 as it can be searched for from the given array of numbers.
the given array of numbers i supplied has to be used as for example i got output of
2 + 1 + 67 + 96 = 165 but it actually sums up to 166 and as such should not print yet somehow despite my condition it goes ahead to print which leaves me a bit confused.
and subsequent sums printed out are not correct yet it prints despite my condition not to print if it is not equal to 165.
i try to make the code faster by summing the numbers up the element excluding the last element and then as the last element is changing i simply add sum to it so this way i dont have to go through the entire array summing again everytime the last element is changed.