Python递归函数中列表传参困惑——以combinationSum2实现为例

Hey there! Let's clear up your confusion around how lists are passed in Python recursion, using your combinationSum2 code as a reference. The core issue here boils down to how Python handles mutable objects like lists when passing them to functions.

The Key Problem: Mutable References #

In Python, lists are mutable, which means when you pass path to your dfs function, you're passing a reference to the same list instance, not a copy. That means every time you modify path (like appending or popping elements), all places that hold that reference—including the entries you added to res—will see those changes.

Looking at your code, when you do res.append(path), you're storing a reference to the live path list. Later, when you call path.pop() (either in the target < 0 branch or elsewhere), you'll accidentally modify the list you already saved in res—definitely not what you want!

Fixing Your Code Step-by-Step #

Let's adjust your dfs function to handle this correctly, plus fix some other common backtracking pitfalls:

1. Save a Copy of path When Target is Met #

Instead of appending the live path reference to res, append a copy of its current state. You can do this with path.copy() or list(path):

if target == 0:
    res.append(path.copy())  # Save a snapshot of the current path
    return

2. Fix Backtracking Logic #

Your current target < 0 branch only pops an element in that specific case, which breaks the symmetry of backtracking. In standard backtracking, you should:

• Add an element to path
• Recurse with the updated state
• Always pop the element afterward (to undo the change and explore other possibilities)

Also, since you sorted candidates upfront, we can add two optimizations:

• Skip duplicate elements to avoid duplicate combinations
• Prune the loop early if the current element is larger than the remaining target (since the list is sorted, all subsequent elements will be bigger too)

Here's the revised dfs function:

def dfs(self, start_index, target, path, res, candidates):
    if target == 0:
        res.append(path.copy())
        return
    if target < 0:
        return  # No need to pop here—we'll handle it in the loop
    
    for i in range(start_index, len(candidates)):
        # Skip duplicates: don't pick the same element as the previous one (if we're past start_index)
        if i > start_index and candidates[i] == candidates[i-1]:
            continue
        # Prune: if current element is bigger than remaining target, break early
        if candidates[i] > target:
            break
        
        # Backtracking step: add, recurse, remove
        path.append(candidates[i])
        # Move to next index (i+1) since we can't reuse the same element twice
        self.dfs(i + 1, target - candidates[i], path, res, candidates)
        path.pop()  # Undo the append to explore other combinations

Recap of List Passing Best Practices for Recursion #

• Always save copies of mutable objects when you want to preserve their state at a specific point in recursion. Storing references will lead to unexpected changes later.
• Keep backtracking symmetric: Every time you add an element to your path, make sure you pop it after the recursive call—this ensures your path is reset correctly for the next iteration.
• Use sorted input to enable pruning and duplicate skipping, which makes your backtracking more efficient.

内容的提问来源于stack exchange，提问作者xman