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)
0 Comments:
Post a Comment
Note: Only a member of this blog may post a comment.