# Thread: Help with recursive algorithm

1. ## Help with recursive algorithm

I have to do a program that reads a list of positive numbers (5,3,6...) and a target. The program should find the target value (if posible) through combinations of sums and differences of the given number list. Also it should store in an array the combination of numbers and its sign. This is what I have:

Code:
``` void findobj(int j)
{
int i,temp;

i = 0;

do{
i++;
if (numbers[i] != KEY)
{
//the variable "sum" stores the sum of the combination numbers
sum+= numbers[i];

//stores solution numbers
solution[j] = numbers[i];
temp = numbers[i];

//KEY is a macro wich value is -1,
//it  prevents the program from selecting
//the same number twice
numbers[i] = KEY;

if (j < N)
{
findobj(j+1);
numbers[i] = temp;

if (sum != objetive)
{
sum-=numbers[i];
solution[j] =  -(numbers[i]);

}
}
}
}while ((i < N) && (sum != objetive));

return;
}```
The problem is that the program doesnt find all the combinations, for example, given the following list (2,3,10,4,8) and target = 16, the variable sum never reaches the target, (the combination of numbers to reach the target is 2,10,4) but if the target = 15, the variable sum reaches the target.

Thanks.

2. So in other words you don't implement code to skip over numbers.

3. I tried to read the code, but I must admit I don't understand well how it works
For instance, you use some variables defined elsewhere and not in the same function, numbers, solution, N, etc(I guess global variables)
Also I see you use recursivity, but, you use it in a way hard to understand and prone to errors, instead to make the function returns some value, you make the function modify a global array. So it's not clear what is the END condition.
You have here a problem of path finding, if I understood well, you have a list of numbers (n1,n2,n3..nN) and a target T, you have to sum them to get the final T (make combinations)
There are algorithms to do that like the Tree Search (I guess the variant InDepth would fit for you)

I would advise to review your algorithm more than try to tune this one.

--------------------
http://www.uberum.com

4. I think this is known as the "backpack problem"; you might want to try googling it: http://www.google.ca/search?hl=en&q=...e+Search&meta=

 The first hit has a solution or two: http://www.edm2.com/0601/backpack.html [/edit]

5. I believe this is actually called the 0-1 Knapsack problem. You can look up that along with recursion...but I think you'll probably just find dynamic programming solutions to that one.