znight - 4 months ago 9

Python Question

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

Source (Stackoverflow)

Comments