Python + Leetcode: Test cases are "leaking over"/"interfering" with each other for recursive problems/code solutions?

47 views Asked by At

So I was working on Leetcode #39-Combination Sum . And my test cases appear to be "leaking over/interfering" (best choice of words I could come up with) with each other:

For example, when I run the first test case (candidates = [2,3,6,7]; target = 7), it passes successfully with the output being [[2,2,3],[7]] ✅.

However, when I run the 2nd test case (candidates =[2,3,5]; target = 8), it doesn't pass ❌. The output [[2,2,3],[7],[2,2,2,2],[2,3,3],[3,5]]. Strangely, I noticed that [2,2,3] and[7] are not only wrong because they don't sum up to target =8, but they are the output arrays of the previous test case.

Likelwise, when I run the 3rd test case (candidates=[2], target=1), my output [[2,2,3],[7],[2,2,2,2],[2,3,3],[3,5]], which is not only completely wrong❌ but also exactly the same as the last test case's output. This is even stranger bc how can a [2] and target=1 produce 5 different combos with numbers containing 3,5,7 which aren't even in candidates = []?

I wrote my code in Python, and I utilized a recursive backtracking solution (note-I did not use inner functions-not sure how much of a difference that would make otherwise though?):

import copy
class Solution(object):
    result = []
    def dfs(self, index, cur_list, total_sum, candidates, target):
        if total_sum == target:
            self.result.append(copy.copy(cur_list))
            return
        if total_sum > target or index >= len(candidates):
            return
        cur_list.append(candidates[index])
        self.dfs(index, cur_list, total_sum + candidates[index], candidates, target)
        cur_list.pop()
        self.dfs(index + 1, cur_list, total_sum, candidates, target)

    def combinationSum(self, candidates, target):
        self.dfs(0, [], 0, candidates, target)
        return self.result
0

There are 0 answers