find n sum in an array recursively please ..

[codezy]

hii ,,

i have a sorted array x[]={1,2,10}, and a "target" i want to search recursively for the sum of the elements of the array with any combination without any repetition of elemt in the array (i.e. if target=11 then we can get it from the array (1+10) but if the target=14 we can't get this sum)

Can anyone help me with this, please ?

[R0mai]

http://www.cplusplus.com/articles/how_to_ask/

[Duthomhas]

This is a standard algorithms homework.

You must solve it yourself.

Once done that, you can work with making it happen in C++. When you get stuck, post your attempts and we will help you fix the C++ code to agree with your solution.

[codezy]

i tried it and this is my wrong attemp ..

bool sol(int target,int stInd)
{
    if(target==0) 
       return true;
    if(target<0) 
       return false;
    for(i=stInd;i<4;i++)
       if(sol(target-x[i],i+1)) 
           return true;
    return false;
} 

[buffbill]

Do you mean that if you had an array with elements 1-20 and the target was 14 that it would find 1+5+8,10+4,2+12 etc...? or do you mean 1+13,2+12,3+11,4+10,etc....? or do you mean something else?

[jsmith]

@codezy:

Think about it this way.

Suppose I had the array { 1, 2, 3, 4, 5, 10, 15, 20, 50 }

and wanted to search for the sum 42.

I look at the first element in the array -- 1. 1 is less than 42, so now I can
reduce the problem to searching for the sum 42 - 1 = 41 in the array
{ 2, 3, 4, 5, 10, 15, 20, 50 }, which is essentially the same problem, just
with a smaller value and a smaller array.

See the recursion?

[codezy]

@ buffbill ... any cobmination i want to if this sum exist with any possible way ..

@ jsmith ... i made a a=way to do this but in complexity O(2^N) and this is too much if n>25 ,, Anyone had an algorithm to reduce this complexity >>?

bool rec( int i , int sum , int target ) 
{
   if( sum == target )return 1; 
   if( i == n )return 0;
   if( rec(i + 1 , sum , target) || rec(i + 1 , sum + x[ i ] , target) )return 1;
   return 0;
}

[jsmith]

You should be able to do this with an OR.

Let's say I have an array sorted in ascending order.
{ x1, x2, x3, x4, ... , xn }

If x1 is greater than the sum, then there exists no solution.
If x1 is less than the sum, then consider x1 to be part of the solution, and
reduce the problem to finding the sum "sum - x1" in the array { x2, x3, x4, ...., xn }
If x1 equals the sum, then you have the solution.

Notice: three if() statements and one recursive call.

Your solution is three if() statements and two recursive calls.