backtrack algorithm

[AmaScatman]

hi all..
i need help in solving a backtrack algorithm using c++ .

the program asks the user for a number , and the output will be all the sums of the number entered.. for example:

if the user entered 10.. the output should be:
1+2+3+4
1+2+7
1+3+6
1+4+5
1+9
2+3+5
2+8
3+7
4+6
10

example 2.. if the user entered 6.. the output should be:
1+2+3
1+5
2+4
6

[Scipio]

Your missing one point i guess: the next number in the sum sould be bigger then the one before (otherwise you could write 10 also as 1+1+1...)

Try to find the patern:
number=1+a
a=2+b
b=3+c
etc...

Maybe you could use a recursive function?

[Zaita]

+1 for Recursion

[firedraco]

I third that...recursion should work as long as you can get all the possibilities.

[easytiger]

#include <vector>
#include <iostream>

using namespace std;

vector<vector<int> > backtrack(const int n, const int min)
{
vector<vector<int> > result;
if(n > 2 && min < (n + 1) / 2)
{
for(int i = min; i < (n + 1) / 2; i++)
{
vector<vector<int> > temp = backtrack(n - i, i + 1);
for(size_t j = 0; j < temp.size(); j++)
{
vector<int> aaa;
aaa.push_back(i);
for(size_t k = 0; k < temp[j].size(); k++)
aaa.push_back(temp[j][k]);

result.push_back(aaa);
}
}

}
vector<int> vec;
vec.push_back(n);
result.push_back(vec);
return result;

return result;
}

void main()
{
vector<vector<int> > vec = backtrack(10, 1);
for(size_t i = 0; i < vec.size(); i++)
{
for(size_t j = 0; j < vec[i].size(); j++)
cout << vec[i][j] << " ";
cout << endl;
}

getchar();
}

[AmaScatman]

thx easytiger for the code... but i can't use <vector>
so plz could u modify ur code...

i tried to do a recursive function.. here is my code:

#include <iostream.h>
#include <conio.h>

int val=0,start=0;

void sumAlgo(int n){

if(start==n){ cout<<n; return ;}

val=0;
start++;

for(int i=0 ; i<n ; i++){
val=start+i;
if(n == val && i>start) cout<<start<<"+"<<i<<endl;
}

sumAlgo(n);
}


main(){
int numb;
cout<<"enter a number :";
cin>>numb;

sumAlgo(numb);
getch();
}


but i can only view 2 numbs... for example..
if the user entered 10 the output would be:
1+9
2+8
3+7
4+6
10

any ideas??

[jsmith]

What data structures can you use?

The solution I came up with was less than half the size of the solution posted above, required far less storage, but outputted answers as soon as it found them as opposed to computing all of them and outputting all of them at the end. But even my solution used a vector. However I could easy replace the vector with a string instead.

Are you allowed to use arrays? strings?

[AmaScatman]

yeah, sure jsmith .. i can use arrays or strings......

plz could u post ur code.

[jsmith]

Well, I don't do peoples' homework assignments for them. Anyway, I could post it, but you wouldn't be able to use it anyway because 1) I use vectors and you aren't allowed to, and 2) I used a bit of boost::lambda along with STL algorithms.

So if you can use arrays, then you could just start with the above code and replace the vectors with arrays.