遞歸函數調用 - 生成排列和回溯

我有一個字符串矢量，所有相同的大小。
我必須建立一個滿足一些條件的字符串列表作爲解決方案。遞歸函數調用 - 生成排列和回溯

的僞代碼的算法是這樣的：

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;

}

問題是解決方案在沒有控制的情況下不斷增長。你能告訴我如何處理它嗎？並做一個適當的回溯？

來源

2011-02-05 ouroboros84

這樣比較好...`for（word = dictionary.begin（）; word 2011-02-05 19:22:16

@muntoo：爲什麼會更好？ – sth 2011-02-05 19:24:58

一個問題是您在修改dictionary的同時迭代它。修改矢量會使該矢量的迭代器無效，因此word在下次使用時不再有效。這可能會導致崩潰或失敗。但erase函數返回一個新的有效迭代器，您可以使用它繼續迭代。

此外，您基本上會從回溯函數中刪除dictionary中的所有元素，並且相當快，在dictionary中將不會留下任何元素。可能你想在遞歸調用返回之後重新添加擦除的元素？

來源

2011-02-05 19:31:15 sth

遞歸函數調用 - 生成排列和回溯

回答

相關問題