Recursive function calls - generate permutations and backtracking
I have a vector of strings, all of the same size.
I have to build as a solution a list of strings that fulfill some conditions.The pseudo code algorithm would be something like this:
backtrack(N)
if solution_valid()
print solution
else
for each word in vector
if(possible candidate)
backtrack(N+1)
I get lost in how to actually write the code.
I do not understand how to save current solutions, what 开发者_如何学Ckind of parameters to pass to the function...
Here is something I have though I think it's completely wrong:
int backtrack(vector<string> &dictionary, vector<string> &solution, int current_row)
{
cout << "current row: "<< current_row << " of: " << rows << endl;
if(current_row == rows /*&& square_completed(solution)*/)
{
vector<string>::iterator word;
for(word = solution.begin(); word != solution.end(); ++word)
{
cout << *word << endl;
}
return 0;
}
vector<string>::iterator word;
for(word = dictionary.begin(); word != dictionary.end(); ++word)
{
backtrack(dictionary,solution,current_row+1);
solution.push_back(*word);
}
return 1;
}
problem is that solution keeps growing without control. Could you tell me how to deal with it? and do a proper backtracking?
One problem is that you modify dictionary
while iterating over it. Modifying a vector invalidates iterators of that vector, so word
is no longer valid when you use it the next time. This might crash or otherwise fail. But the erase
function returns a new valid iterator, you can use that to continue iterating.
Also you basically erase all elements from dictionary
in the backtrack function and quite fast there will be no element left in dictionary
. Probably you want to re-add the erased elements after the recursive call returns?
精彩评论