anryhuang
BAN USERstock trader...
a general backtrack in c++
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void print(vector<int> v){
for(int i = 0; i < v.size(); ++i )
cout<<v[i]<<" ";
cout<<endl;
}
bool isSolution(vector<int> s, int step, int n){
return step == n;
}
void processSolution(vector<int> s, int step, int n){
print(s);
}
void generateSpace(vector<int> s, int step, int n, vector<int> &space){
vector<int>::iterator sBegin = s.begin();
vector<int>::iterator sEnd = s.end();
int key = -1;
if(s.size()>0)
key = s.back(); // s.back() is unstable when s is empty
for(int i=1; i <=n; i++){
if( find(sBegin,sEnd, i) == sEnd and i != key-1)
space.push_back(i);
}
}
void backtrack(vector<int> s, int step, int n){
if( isSolution( s, step, n) ){
processSolution(s,step,n);
}
else{
++step;
vector<int> space;
generateSpace(s,step,n,space);
for(int i = 0;i < space.size(); i++){
s.push_back( space[i] );
backtrack(s,step,n);
s.erase(s.end()-1);
}
}
}
int main(){
vector<int> s;
int step = 0;
int n = 3;
backtrack(s,step,n);
return 0;
}
it is easy to find max value via recursion,
it is a little tricky to pass the path information. The recursive function returns the max sum of the current tree, and uses a reference to return the path generating the sum at the same time.
- anryhuang February 13, 2013