DFS中c++和Python的区别

Question

目前我正在研究 Leetcode 问题 39 组合和，并尝试在 C++ 和 Python 中解决它。

该算法是一个基本的 DFS，我的问题是关于 dfs 部分。当我将C++中的代码复制到Python时，它似乎不起作用。以下是Python中的self.dfs部分：

    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 中得到了一个空列表。然而，如果我将最后 "else" 部分更改为：

    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();
      }
     }
    }

Answer 1

在您的 C++ 代码中，当您执行以下操作时：

res.push_back(comb);

你正在复制 comb 的数据（因为 res 是整数的 "list" of "list"），即使 comb 被传递作为参考。

在您的 python 代码（第一个片段）中，您从不复制，因此 res 的所有元素都是同一个列表。为了等价，你可以这样做：

res.append(list(comb))

或

res.append(comb[:])

您的修复（递归调用函数时传递副本）有效，但即使不需要也制作副本。您只需要在附加到 res

时制作副本

（要在 C++ 中重现 "bug"，您必须在向量指针上创建一个向量并存储 comb 的地址，这样就不会进行任何复制）

DFS中c++和Python的区别

difference between c++ and Python in DFS

c++

python

depth-first-search