c++ - 递归函数调用——生成排列和回溯

Question

我有一个字符串 vector ，大小都相同。
我必须构建满足某些条件的字符串列表作为解决方案。

伪代码算法是这样的:

backtrack(N)
if solution_valid()
    print solution
else
    for each word in vector
        if(possible candidate)
           backtrack(N+1)

我迷失了如何实际编写代码。

我不明白如何保存当前的解决方案，传递给函数什么样的参数......

虽然我认为这是完全错误的，但这是我的一些东西:

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;

问题是解决方案在不受控制的情况下不断增长。你能告诉我如何处理吗？并进行适当的回溯？

Answer 1

一个问题是您在遍历 dictionary 的同时对其进行了修改。修改 vector 会使该 vector 的迭代器失效，因此 word 在您下次使用时不再有效。这可能会崩溃或以其他方式失败。但是 erase 函数返回一个新的有效迭代器，您可以使用它继续迭代。

此外，您基本上在回溯函数中删除了 dictionary 中的所有元素，而且很快 dictionary 中将没有任何元素。可能您想在递归调用返回后重新添加已删除的元素？