CODEWITHSUNDEEP
c++recursionbacktracking
ouroboros84
ouroboros84

Reputation: 131

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

Upvotes: 2

Views: 1535

Answers (1)

sth
sth

Reputation: 229583

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?

Upvotes: 1

Related Questions