Permutation in C++
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > result;
vector<int> sofar;
permutehelper(nums, sofar, result);
return result;
}
void permutehelper(vector<int> &rest, vector<int> &sofar, vector<vector<int>> &ans){
if(rest.size() == 0) {
ans.push_back(sofar);
}
else{
for(int i = 0; i < rest.size(); i++){
sofar.push_back(rest[i]);
rest.erase(rest.begin() + i);
permutehelper(rest, sofar, ans);
}
}
}
};
Wie ändere ich es, um alle Permutationen zurückzugeben? Derzeit gibt es nur [[1,2,3]]. Ich weiß, dass es viele Lösungen gibt, aber ich möchte, dass es mithilfe von Vektoren und Rest funktioniert.
Sie haben nur einen restVektor (und nur einen sofarVektor), weil Sie als Referenz übergeben. Das heißt, wenn Sie ein Element aus entfernen rest, ist es weg. Du legst es nie zurück, also ist es für immer weg. (Tatsächlich entfernen Sie Elemente aus dem Vektor, der als Argument an übergeben wurde permute. Einige würden sagen, dass das Ändern des Arguments ein schlechtes Interface-Design ist.)
Sie möchten wahrscheinlich die Parametervektoren nach Wert übergeben (außer ans, das Ergebnisse akkumuliert und daher dauerhaft geändert werden sollte). Natürlich werden bei der Wertübergabe Kopien erstellt, was eine unnötige quadratische Komplexität mit sich bringt, aber es ermöglicht dem Algorithmus, wie erwartet zu arbeiten.