python - 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 是整数“列表”的“列表”)，即使 comb 作为引用传递。

在您的 Python 代码(第一个片段)中，您永远不会制作拷贝，因此 res 的所有元素都是相同的列表。为了等价，你可以这样做:

res.append(list(comb))

或

res.append(comb[:])

您的修复(递归调用函数时传递拷贝)有效，但即使不需要也制作拷贝。您只需要在附加到 res

时制作一个拷贝

(要在 C++ 中重现“错误”，您必须在 vector 指针上创建一个 vector 并存储 comb 的地址，这样就不会进行任何复制)