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.
Code:
#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);
}
}