Vector modified under recursion.

[rjohansson]

Hi all,

The code below is my attempt to solve the following problem:

Given a vector v of strings find all combinations of them such that their lengths sum up to the number n, and then store them in vector res. For instance if v consists of the strings <up, down, left> and n = 8, we get <down, left> and <up, up, up, up> as two possible solutions. Normally I would do this with a recursive search in Python but now I want to learn som C++. Apparently there is a problem when I try to call with vector local which is a copy of the vector tmp but I dont understand why.

Vector tmp contains those strings that I have collected so far and if they sum to n then I add vector tmp to vector res and return. If their sum is < 0 then I just return, else I take a new string and decrese n with it's length before next call.

void explore(std::vector <std::string> v, int pos, int n, std::vector<int> tmp, std::vector <std::vector <int> > *res){
std::vector<int> local;
copy(tmp.begin(), tmp.end(), local.begin());
if (n < 0){
return;
}
else if (n == 0){
(*res).push_back(local);
return;
}
else{
for (int i = pos; i < v.size(); i++){
local.push_back(i);
explore(v, i, n - v[i].size(), local, res);
}
return;
}
}

[hamsterman]

I compiled it and got an assertion failure. That's because std::copy doesn't allocate space for you, so if tmp is larger than local (which is empty, so anything is larger than it) it's not possible to put on into another. The solution is to simply write "local = tmp". Alternatively you could not use local at all as tmp is already a copy of the vector you passed to explore().

Though the function still doesn't work. It seems that this is because you push to local before calling explore() so even if the child call fails, the string remains in local and if the parent succeeds that string gets added to res.

Also, http://www.cplusplus.com/articles/z13hAqkS/