pythonlistalgorithmdata-structuresbacktracking

Leetcode - Combination sum problem in Python


I am building the logic to the Leetcode - Combination Sum problem. Here is a link to the problem.The problem states:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

My current answer is accepted by the platform.The code looks like this.

def help(self, i, s, c, t,arr,ans):
    if s == t:
        ans.append(arr)
        return
    if i==len(c) or s>t:
        return
    self.help(i+1,s,c,t,arr,ans)

    self.help(i,s+c[i],c,t,arr + [c[i]],ans)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    i=0
    self.help(i,0,candidates, target, [],ans)
    return ans

But when I change the two recursive function calls within the help function to something like this, it fails.

def help(self, i, s, c, t,arr,ans):
    if s == t:
        ans.append(arr)
        return
    if i==len(c) or s>t:
        return
    self.help(i+1,s,c,t,arr,ans)
    arr.append(c[i])
    self.help(i,s+c[i],c,t,arr,ans)
    arr.pop()
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    i=0
    self.help(i,0,candidates, target, [],ans)
    return ans

I don't understand the difference. In both these code blocks I am doing pretty much the same thing. Then why append and pop fails while the other one is getting accepted?


Solution

  • In your first version, you pass a new list in each recursive call because arr + [c[i]] creates a new list. So each element appended to ans is a different list.

    In the second version, you keep modifying the same list in place when you use arr.append(c[i]) and arr.pop(). So all elements of ans are references to the same list.

    If you use ans.append(arr[:]) you make a copy of this list, so the later arr.pop() doesn't affect it.