# trying to understand my code in terms of recursion

#### maicael

##### New member
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];
}
}
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");
}
}``````
the code above i am trying to use to understand recursion but the thing is when it trys to generate the possible combination of numbers that add up to 165 it gives me wrong combinations when numberOfsubsets = 4.
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.

It's time to learn how to debug. You generally don't find errors in any but the simplest code by just reading the code. You need to run it and examine it while it's in action. That's debugging.

So, start by placing a breakpoint at the top of your code. When you run the project and execution gets to that point, it will break. You can then use the Autos, Locals, Watch and Immediate windows and numerous other tools to examine the state of the application. You can then continue running the code normally or step through it line by line. Stepping gives you the opportunity to see whether execution follows the path you expect and also whether the state meets your expectations after the step. As soon as what actually happens doesn't match your expectations, you've found an issue and can then look at why it happened. At the very least, you can provide us with far more relevant information to help us diagnose the issue, i.e. exactly where the issue occurred and what data was in use at the time.

hello
l was able to finally debug it.
the problem was the sum variable declared as static and so it was supposed to be in synchronization with the currentloop variable but along the way both variables went out of synchronization.
i have corrected the code.
C#:
``````[COLOR=#3E3E3E]//ensures that all elements prior to the last element in the array is calculated just once and used
[/COLOR]            //through out until its no longer needed.
if (currentLoop != 0 && currentLoop == (numberOfSubsets - 1))
{
//this part was the problem.
if(sum == 0)
{
sum = checkSumOfNumbers();
}
else
{
sum += inputValues[subset[currentLoop - 1]];
}
}``````

so i change it to
C#:
``````if (currentLoop != 0 && currentLoop == (numberOfSubsets - 1))
{
//this solved the problem
sum = 0;
sum = checkSumOfNumbers();
}``````
this ensures it calculates the whole value from scratch instead of one at a time.

Replies
2
Views
448
Replies
5
Views
1K
Replies
8
Views
450
Replies
4
Views
762
Question fusing 2 codes?
Replies
4
Views
434