[FIXED] How to return the list of all the Subset of a list of integer, using Python?

Issue

I have been given an integer array A, I need to return an array of all it's subset. I have tried to solve this problem using Backtracking.

def subset_helper(index, result, A, temp):
    result.append(temp)
    #print(temp)
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return    
def subsets(A):
    result = []
    temp = []
    index = 0
    subset_helper(index, result, A, temp)
    return result

This returns me an Empty list. Printing temp gives me right answer, but the problem asks me to return an array. I Guess the temp array due to call by reference is getting changed at each iteration and that's probably the reason it's giving me list of empty list.

Input : [12,13]
Expected Output : [[],[12],[12,13],[13]]
My Output : [[],[],[],[]]

Solution

you can try to print address in subset_helper, and you can found that your temp is the same object address, that's why your result is a list of same object value:

def subset_helper(index, result, A, temp):
    result.append(temp)
    print(id(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return  

output:

1559293711304
1559293711304
1559293711304
1559293711304
[[], [], [], []]

now, changes to append the copy of your tmp object:

import copy
def subset_helper(index, result, A, temp):
    result.append(copy.copy(temp))
    for i in range(index,len(A)):
        temp.append(A[i])
        subset_helper(i+1,result,A,temp)
        #backtracking
        temp.pop()
    return    

and now you append an new object to result list, you can see the output as you expected :

[[], [12], [12, 13], [13]]

Answered By - Zhubei Federer

Answer Checked By - Willingham (PHPFixing Volunteer)