difference between c++ and Python in DFS

Question

Currently I am working the Leetcode Problem 39 Combination Sum, and trying to solve it in Both C++ and Python.

The Algorithm is a basic DFS, my question is about the dfs part. When I copied the code in C++ to Python, it didn't seem to work. The following is the self.dfs part in 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()

In this code, I got empty list in the res. Yet, if I changed the last "else" part to:

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

it did work.

So I am wondering it might be the difference between Python and C++, maybe the use of reference? Anyone who could figure it out?

To be convenient, I also attach the C++ code here:

    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

In your C++ code, when you do:

res.push_back(comb);

you're copying the data of comb (since res is a "list" of "list" of integers), even if comb is passed as reference.

In your python code (first snippet), you never make a copy, so all elements of res are the same list. For that to be equivalent, you could do:

res.append(list(comb))

or

res.append(comb[:])

Your fix (passing a copy when calling the function recursively) works but makes a copy even if not needed. You only need to make a copy when you append to res

(to reproduce the "bug" in C++ you'd have to create a vector on pointers of vectors and store the address of comb so no copy is done)