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 integertarget
, return a list of all unique combinations ofcandidates
where the chosen numbers sum totarget
. 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?
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.