0

I was doing a bit of Leetcode and do not understand why res.append(subset) does not append the subset to res. Could somebody explain the reason behind this?

def solve(arr):
    res = []
    def dfs(arr,subset):
        if len(arr) == 0:
            # why does the following line not append the subset to res?
            res.append(subset)
        for i in range(len(arr)):
            subset.append(arr[i])
            dfs(arr[:i] + arr[i+1:],subset)
            subset.pop()
    dfs(arr,[])
    return res
Max Gabriel
  • 23
  • 5

1 Answers1

0

Your problem is that you have assumed that res.append(subset) will append the items in subset. Python assignments for compound objects behave differently and so appending a list to a list is not the same as appending the values of a list to a list.

In this example, subset.pop() is removing values from subset and hence res, so that finally solve returns a list of empty lists. To make minimal changes to your code, I suggest that you copy the data using copy.deepcopy().

import copy
def solve(arr):
    res = []
    def dfs(arr,subset):
        if len(arr) == 0:
            # copy, rather than reference
            res.append(copy.deepcopy(subset))
        for i in range(len(arr)):
            subset.append(arr[i])
            dfs(arr[:i] + arr[i+1:],subset)
            subset.pop()
    dfs(arr,[])
    return res

More information is available in the docs and there are simple examples in previous SO answers

tgpz
  • 161
  • 10