recursion - Generating All Subsets of a Set Using Recursive Backtracking (Python) -

i'm trying understand backtracking i'm stuck in problem, here's prompt:

given set of distinct integers, return possible subsets.

example input: [1,2,3]

example output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

here's code:

def subsets(nums):     res = []     backtrack(res, [], nums, 0)     return res  def backtrack(res, temp, nums, start):     # print(temp)     res.append(temp)     in range(start, len(nums)):         temp.append(nums[i])         backtrack(res, temp, nums, + 1)         temp.pop() # backtrack 

when return res list of empty lists of size 2^(len(nums)), right size numbers aren't there. printing temp before res.append(temp) shows temp carrying right output.

e.g.

res = [[], [], [], [], [], [], [], []]

print statements:

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

why changes not carrying on res list?

edit 1:

this solution works, what's difference?

def subsets(nums):     res = []     backtrack(res, [], nums, 0)     return res  def backtrack(res, temp, nums, start):     # print(temp)     res.append(temp)     in range(start, len(nums)):         backtrack(res, temp + [nums[i]], nums, + 1) 

you're appending multiple references same list object res. can demonstrate doing

result = subsets([1, 2, 3]) print([id(u) u in result]) 

that print list of 8 identical ids.

so various changes make temp "lost", , final contents of res 8 references whatever final value of temp is, , in case it's empty list.

---

the simple way fix append copies of temp res.

def subsets(nums):     res = []     backtrack(res, [], nums, 0)     return res  def backtrack(res, temp, nums, start):     res.append(temp[:])     in range(start, len(nums)):         temp.append(nums[i])         backtrack(res, temp, nums, + 1)         temp.pop() # backtrack  print(subsets([1, 2, 3])) 

output

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

---

fwiw, realise main point of exercise practice recursion, in python it's better avoid recursion unless need (eg, processing recursive data structures trees). here's more compact iterative solution.

def subsets(seq):     z = [[]]     x in seq:         z += [y + [x] y in z]     return z 

to see how works, can expand little, , add print call.

def subsets(seq):     z = [[]]     x in seq:         print('z =', z, 'x =', x)         w = []         y in z:             w += [y + [x]]         z += w     return z  result = subsets([1, 2, 3]) print(result)   

output

z = [[]] x = 1 z = [[], [1]] x = 2 z = [[], [1], [2], [1, 2]] x = 3 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

we start list z containing single empty list.

on each loop create new list w looping on z , making each item in w copy of corresponding item in z current x appended it. extend z contents of w.

---

just fun, here's iterative generator produces subsets (in natural order) bitstrings. method quite efficient, , it's if want subsets of large sequence without consuming lot of ram.

def subsets(seq):     w = len(seq)     in range(1<<w):         yield [u u, v in zip(seq, reversed('{:0{}b}'.format(i, w))) if v=='1']  print(*subsets([1, 2, 3])) 

output

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