Recursive Problem.

[penance]

Hello. I am trying to write a recursive program that will check partitions of an array to see if they add up to a certain number. A person gives the target number, the length of the array, and the numbers in the array, and then the program will check combinations of the numbers in the array and print out how many possible combinations give the desired target number. For example, in a set of 1, 4, and 5, with the target number 5, it will give back 2 solutions, because a partition of 1 and 4 adds up to 5, and a partition of 5 adds up to 5.

This is the code I have so far, but it's not giving the proper result, and I believe it has to do with the fact that I have it stop when the size of the array equals 0, which seems to force it to quit searching before it has checked all the combinations. However, I don't know what condition to put in place in order to get it to stop at the right place and give the desired result. I've tried doing many things but nothing seems to work and I would appreciate it if someone could help me figure out how to get this code finished.

Thanks for any help anyone can give me, and if no help can be given then I thank you for your time.

#include <stdio.h>

int NumberofPartitions (int *set, int size, int result, int parts);

int main ()
{
	int target;
	int n;
	int number;
	int length;
	int array[100];
	int *start = &array[0];
	int partitions = 0;

	printf("Enter target number: ");
	scanf("%d", &target);

	printf("Enter array length: ");
	scanf("%d", &length);

	printf("Enter numbers for the array: ");
	for (n = 0; n < length; n++) {
		scanf("%d", &number);
		array[n] = number;
	}

	partitions = NumberofPartitions(start, length, target, partitions);
	printf("Number of partitions equals %d.\n", partitions);
}

int NumberofPartitions(int *set, int size, int result, int parts) {

	int guide;

	if (size == 0) {
		return parts;
	}

	else if (*set - result == 0) {
		parts++;
	}

	else {
		guide = *set;
		*set++;
		size = size - 1;
		NumberofPartitions(set, size, result, parts);
		NumberofPartitions(set, size, (result - guide), parts);
	}

}

[grumpy]

I'm not clear on exactly what you're trying to achieve, but if size is non-zero the function does what a friend of mine describes as "dropping off the end" --- there is no return statement in the other cases.

One of the effects of that is: if you call NumberOfPartitions() from other code (eg in main()), it will always return the the value of parts.

[penance]

I'm not clear on exactly what you're trying to achieve, but if size is non-zero the function does what a friend of mine describes as "dropping off the end" --- there is no return statement in the other cases.

One of the effects of that is: if you call NumberOfPartitions() from other code (eg in main()), it will always return the the value of parts.

Well, I'm not sure if it needs a return statement in the other cases. See NumberOfPartitions is supposed to be a recursive function.

For example, let's say the array given by the user is 1, 3, 4, 5 and the target number is 5. The NumberOfPartitions function is given the target number 5, the length 4, and the array of 1, 3, 4, 5 and it's supposed to find how many number combinations in the array create 5.

So the program starts out by assuming that 1, the first number in the array, is either part of the solution or not. So the pointer to the first number in the array is moved to the second number in the array, and the function calls itself with the array 3, 4, 5, the length 3, and the target number 5 and also calls itself with the array 3, 4, 5, the length 3, and the target number 4. This is because 1 is either part of a solution or not.

The function continues in this fashion until the array is "empty". The way it moves through the array and finds the solutions should look like a binary tree pattern.

Like, if we start with array 1 4 5 and 5 is the target number then the function should go through the array like this

                                1 4 5, 5
                       4 5, 4             4 5, 5
             5, 0         5, 4         5, 1        5, 5
     -5        0       -1      4    -4     1    0        5

And end up with two solutions.

What I want is for the function to raise parts by 1 each time it finds a solution, and then when it goes through all the possibilites in the array, it unwinds and returns the parts. In the example above, it would bring back 2.

I thought that if I kept track of the array length as it went through the function and subtracted 1 from it each time that it would unwind when the array length equals 0 and bring back the answer, but it's unwinding too early, probably because it unwinds as soon as it hits 0 instead of going through all the possibilities when it reaches 0, and thus it's not giving the right answer.

I don't know how to fix this all up to make it do what I want it to do.

[penance]

So, anyone want to take a shot at it? I'm still trying variations. Any help would be appreciated.

[penance]

Never mind, I solved the problem myself. It turned out that the solution was to do this:

#include <stdio.h>

int NumberofPartitions (int *set, int size, int result, int parts);

int main ()
{
	int target;
	int n;
	int number;
	int length;
	int array[100];
	int *start = &array[0];
	int partitions = 0;

	printf("Enter target number: ");
	scanf("%d", &target);

	printf("Enter array length: ");
	scanf("%d", &length);

	printf("Enter numbers for the array: ");
	for (n = 0; n < length; n++) {
		scanf("%d", &number);
		array[n] = number;
	}

	partitions = NumberofPartitions(start, length, target, partitions);
	printf("Number of partitions equals %d.\n", partitions);
}

int NumberofPartitions(int *set, int size, int result, int parts) {

	int guide;

	if (*set - result == 0) {
		parts++;
		return parts;
	}

	else if (size == 0) {
		return parts;
	}

	else {
		guide = *set;
		*set++;
		size = size - 1;
		return parts + NumberofPartitions(set, size, result, parts) + NumberofPartitions(set, size, (result - guide), parts);
	}

}

And it works fine now. It seems so obvious now that I think about it.