Recursion function (subset) returns empty (python)

Question

I wrote a recursion function to get all subsets out of a list of integers. For example, given a list [1, 2, 3], the return will be [[],[1],[2],[3],[1, 2],[1, 3],[2, 3],[1, 2, 3]].

Here is my code:

def subsets(nums):

    def helper(subset, i):

        if i == len(nums):
            print('return = ', subset)
            res.append(subset)

        else:
            helper(subset, i+1)
            subset.append(nums[i])
            helper(subset, i+1)
            subset.remove(nums[i])

    res = []
    helper([], 0)
    return res

I print out the subset in each recursion and they are right. However, the final return res is always empty.

return =  []
return =  [3]
return =  [2]
return =  [2, 3]
return =  [1]
return =  [1, 3]
return =  [1, 2]
return =  [1, 2, 3]
res = [[], [], [], [], [], [], [], []]

Anyone knows why? Appreciate it!

You might be interested in itertools.combinations

jedwards
– jedwards

2018-10-12 02:58:09 +00:00
Commented Oct 12, 2018 at 2:58 — jedwards
– jedwards, Commented Oct 12, 2018 at 2:58

jedwards · Accepted Answer · 2018-10-12 03:03:25Z

7

Pretty close! The issue is that subset is being appended to res, but later modified. What you want is a "frozen" version of what subset is then, not a "reference" to what it will eventually be.

So instead of res.append(subset), consider appending a copy of the list, for example with:

res.append(subset[:])

And you'll get your expected result:

[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

answered Oct 12, 2018 at 3:03

jedwards

30.4k3 gold badges69 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

beepretty Over a year ago

Thanks a lot, @jedwards!

Collectives™ on Stack Overflow

Recursion function (subset) returns empty (python)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related