Confusing about passing list in recursion function of python

Question

class Solution(object):
def combinationSum2(self, candidates, target):
    """
    :type candidates: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    candidates.sort()
    res = []  # save the result
    path = []  # save each unique combination
    self.dfs(0, target, path, res, candidates)
    return res

def dfs(self, start_index, target, path, res, candidates):
    if target == 0:
        res.append(path)
        return
    if target < 0:
        path.pop()
        return
    for i in range(start_index, len(candidates)):
        if i > start_index and candidates[i] == candidates[i-1]:
            continue
        path += [candidates[i]]
        self.dfs(i+1, target-candidates[i], path, res, candidates)
        if path:
            path.pop()

The above code for LeetCode problem Combination Sum II, given the input [10,1,2,7,6,1,5] and 8, the output should be [[1,1,6],[1,2,5],[1,7],[2,6]]. However, the output of this piece of code run to be [[],[],[],[]], I'm very confusing and wondering why :(

Possible duplicate of [How to clone or copy a list?](https://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list) — Aran-Fey, Apr 11 '18 at 11:34
@Aran-Fey according to other posts, everything passing to function in python is said to be "Call by Object Reference", I know the deep copy ad shallow copy of python, just wondering that in my case, why the `path` passing to the backtracking function is not treated as reference? — xman, Apr 11 '18 at 11:42
It _is_ being treated as a reference. That's why when you call `path.pop()` you're destroying your own output, and in the end all you have is a list of empty lists. You want to add the _current_ value of `path` to the result, so you have to make a copy of it to prevent it from being affected by subsequent `pop()` operations. — Aran-Fey, Apr 11 '18 at 11:45

Confusing about passing list in recursion function of python

0 Answers0