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 ?

3
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by 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 ?

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;
}``````
You shouldn't give free code (refer to Daniweb's rules), and hide you against a sentence like "improve it and the rubbish I gave you will work".

jBat

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 ..

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

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.