Help please (recursion !)

[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 ?

[jBat]

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 ?

first of all the code that i give to you is wrong, but it can be a starting point, you should improve the algorithm to find the positions, maybe some mathematical operation.. i hope it will help.

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <sstream>
#include <vector>

using namespace std;

int main()
{
    int numbers[] = {1,2,10};
    vector<int> positions;

    // calculate the length of the array numbers.
    int elementsinarray = sizeof(numbers)/sizeof(int);

    // insert info
    cout << "Please insert target number." << endl;
    string line;
    getline(cin, line);

    // convert to number
    int target;
    istringstream str(line);
    str >> target;

    // verify
    if (!str)
    {
        cout << "bad input" << endl;
        return EXIT_FAILURE;
    }

    // ok we have the target
    int isum = 0;
    for(int i=elementsinarray-1; i>=0; i--) // we start from the end
    {
        // operate
        if(isum < target)
        {
            isum += numbers[i];
        }

        // verifiquem
        if(isum > target)
        {
            isum -= numbers[i];
            continue;
        }
        else if(isum == target)
        {
            positions.push_back(i);
            break;
        }
        else
        {
            positions.push_back(i);
        }
    }

    // show the vector positions
    if(positions.size() > 0 && isum == target)
    {
        cout << endl << "positions in array to sum the number" << endl;

        // shows us the histori entered
        for(unsigned int i=0; i<positions.size(); i++)
        {
            cout << positions[i] << endl;
        }
    }
    else
    {
        cout << endl << "sorry unable to find the positions!!" << endl;
    }

    return 0;
}

[codezy]

jBat

thank you for your replying ,,
but i want to do this in a recursive way .. the iterative is a bit easier than the recursion .. and I am a very beginner in recursion so i want to do this recursively ..

[nezachem]

So, what have you done so far? Do you need help with the algorithm or with coding?

[codezy]

i made the code but in complexity O(2^N) .. and it's very big if (n>20)

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

Can anyone help me with reducing the complexity ??