разница между C ++ и Python в DFS

Question

разница между C ++ и Python в DFS

В настоящее время я работаю над суммой комбинаций Leetcode Problem 39 и пытаюсь решить ее как на C ++, так и на Python.

Алгоритм является базовым DFS, мой вопрос о части DFS. Когда я скопировал код на C ++ в Python, он, похоже, не работал. Ниже приведена часть self.dfs в Python:

    dfs(self, candidates, target, start, comb, res):
if target == 0:
res.append(comb)
elif target < 0:
return
else:
for i in range(start, len(candidates)):
comb.append(candidates[i])
self.dfs(candidates, target-candidates[i], i, comb, res)
comb.pop()

В этом коде я получил пустой список в Res. Тем не менее, если бы я изменил последнюю часть «еще» на:

    for i in range(start, len(candidates)):
self.dfs(candidates, target-candidates[i], i, comb+[candidates[i]], res)

это сработало.

Так что мне интересно, что может быть разница между Python и C ++, может быть, использование ссылки? Кто-нибудь, кто мог бы понять это?

Для удобства я также прикрепляю код C ++ здесь:

    void dfs(vector<vector<int>>& candidates, int target, int i, vector<int>& comb, vector<vector<int>>& res){
if (target < 0)
return;
else if (target == 0)
res.push_back(comb);
else{
for (int i=start; i<candidates.size(); ++i){
comb.push_back(candidates[i]);
dfs(candidates, target-candidates[i], i, comb, res);
comb.pop_back();
}
}
}

1

c++dfs python

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

В вашем коде C ++, когда вы делаете:

res.push_back(comb);

вы копируете данные comb (поскольку res «список» из «списка» целых чисел), даже если comb передается в качестве ссылки.

В вашем коде Python (первый фрагмент) вы никогда не делаете копию, поэтому все элементы res один и тот же список. Чтобы это было эквивалентно, вы можете сделать:

res.append(list(comb))

или же

res.append(comb[:])

Ваше исправление (передача копии при рекурсивном вызове функции) работает, но делает копию, даже если она не нужна. Вам нужно только сделать копию, когда вы добавляете res

(чтобы воспроизвести «ошибку» в C ++, вам нужно создать вектор на указателях векторов и сохранить адрес comb так что копия не сделана)

0