While working on question 39 of Leetcode, I came across an online solution using recursion that was very concise. So rewrote it.
class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ result,temp = [],[] (sorted(candidates),result,0,temp,target) return result def combinationSumRecu(self, candidates, result, start, temp, target): if target == 0: (temp) # Note that you can't directly append(temp) here, otherwise it's a shallow copy, and then () will pop out the number in result as well while start < len(candidates) and candidates[start]<=target: (candidates[start]) (candidates, result, start, temp,target-candidates[start]) () start += 1 if __name__ == '__main__': print Solution().combinationSum([2,3,6,7],7)
At first I didn't understand (list(temp)) in combinationSumRecu why temp has to add list, because temp itself is a list. but removing list results in an error.
Before it was changed, the result was:
[[2, 2, 3], [7]]
After changing to (temp):
[[], []]
Why is this so? What is list doing here?
First, to verify that temp is a list at each step, we are using the type() function to see its type.
if target == 0: print type(temp),temp,result (temp)
The output is:
<type 'list'> [2, 2, 3] [] <type 'list'> [7] [[7]]
As you can see, temp are all lists. but the second result is incorrect
You can output the correct value for comparison
if target == 0: print type(temp),temp,result (list(temp))
The output is:
<type 'list'> [2, 2, 3] [] <type 'list'> [7] [[7]]
As you can see, the second result should have been [[2,2,3]], but it turned out to be [[7]].
So guessing it might be an append() shallow copy problem.
append(temp) is followed by a () operation. result actually appends a reference to temp. When the value of the address pointed to by temp changes, result will also change.
Verify this with an example:
a = [1,2] b = [3,4] (b) print a () print a
The output result is:
[1, 2, [3, 4]] [1, 2, [3]]
To solve this problem, you need to append a deep copy of temp to result. And list(temp) will return a deep copy of temp.
In addition to using list(temp), you can also use temp[:] to make a deep copy.
This above example of python append and shallow copy is all that I have shared with you, I hope to give you a reference, and I hope you will support me more.