znight - 4 months ago 9
Python Question

# My recursive solution in Python is appending and replacing all current items in answer list with the current list

I am trying to implement a Python solution to the programming question
of finding all subsets in an integer array. I should return an array
that contains all subsets of the integer array with no duplicates and
sorted.

``````def subsetHelper(cur_set, index, A, ans):
if index >= len(A):
print "appending ", cur_set
ans.append(cur_set)
print "ans: ", ans
return
# don't include current number
subsetHelper(cur_set, index+1, A, ans)

# include current number
cur_set.append(A[index])
subsetHelper(cur_set, index+1, A, ans)
cur_set.pop()

def subsets(A):
A.sort()
ans = []
cur_set = []
# dont include current number
subsetHelper(cur_set, 0, A, ans)
return ans
``````

Implementing this same logic in C++ results in the correct return value. However when I do this in Python all I get are a collection of empty lists at the very end, while during iteration it's copying the same current list to all items in the list, even though the print out shows its appending the correct subset each time. Why is this happening? Here is the output:

``````print subsets([1,2,3])
appending  []
ans:  [[]]
appending  [3]
ans:  [[3], [3]]
appending  [2]
ans:  [[2], [2], [2]]
appending  [2, 3]
ans:  [[2, 3], [2, 3], [2, 3], [2, 3]]
appending  [1]
ans:  [[1], [1], [1], [1], [1]]
appending  [1, 3]
ans:  [[1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]]
appending  [1, 2]
ans:  [[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]]
appending  [1, 2, 3]
ans:  [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[], [], [], [], [], [], [], []]
``````

there are 2 problem here: the problem first is that you `ans.extend` instead of `ans.append`, once change that we get the second problem which is empty list at the end and the reason is that append only add to the list `ans` a reference to `cur_set` which you end up removing all element in the course of the recursion so you end up with several references to the same list that is empty at the end, to fix this you only need to append a copy of the current content of the list with `list(cur_set)` for instance.

Also there is no reason to make this a class

``````def subsetHelper(cur_set, index, A, ans):
if index >= len(A):
print "appending ", cur_set
ans.append(list(cur_set))  # <--- here was the problem
print "ans: ", ans
return
# don't include current number
subsetHelper(cur_set, index+1, A, ans)

# include current number
cur_set.append(A[index])
self.subsetHelper(cur_set, index+1, A, ans)
cur_set.pop()

def subsets(A):
A.sort()
ans = []
cur_set = []
# dont include current number
subsetHelper(cur_set, 0, A, ans)
return ans
``````

test

``````>>> subsets([1,2,3])
appending  []
ans:  [[]]
appending  [3]
ans:  [[], [3]]
appending  [2]
ans:  [[], [3], [2]]
appending  [2, 3]
ans:  [[], [3], [2], [2, 3]]
appending  [1]
ans:  [[], [3], [2], [2, 3], [1]]
appending  [1, 3]
ans:  [[], [3], [2], [2, 3], [1], [1, 3]]
appending  [1, 2]
ans:  [[], [3], [2], [2, 3], [1], [1, 3], [1, 2]]
appending  [1, 2, 3]
ans:  [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
>>>
``````