znight 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]]
[[], [], [], [], [], [], [], []]

Answer

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]]
>>> 
Comments