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

Question

I'm trying to understand backtracking but I'm stuck in this problem, here's the prompt:

Given a set of distinct integers, return all possible subsets.

Example input: [1,2,3]

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

Here's my code:

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    # print(temp)
    res.append(temp)
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

when I return res I get a list of empty lists of size 2^(len(nums)), which is the right size but the numbers aren't there. However printing temp before I do res.append(temp) shows that temp is carrying the right output.

E.g.

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

print statements:

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

Why are the changes not carrying over to the res list?

Edit 1:

This solution works, what's the difference?

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

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

Undergarment

Answer 1

You're appending multiple references to the same list object to res. We can demonstrate this by doing

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

That will print a list of 8 identical IDs.

So the various changes that you make to temp get "lost", and the final contents of res will be 8 references to whatever the final value of temp is, and in this case it's the empty list.

---

The simple way to fix this is to append copies of temp to res.

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    res.append(temp[:])
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

print(subsets([1, 2, 3]))

output

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

---

FWIW, I realise that the main point of this exercise is to practice recursion, but in Python it's better to avoid recursion unless you really need it (eg, for processing recursive data structures like trees). But here's a more compact iterative solution.

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

To see how this works, we can expand it a little, and add a print call.

def subsets(seq):
    z = [[]]
    for x in seq:
        print('z =', z, 'x =', x)
        w = []
        for 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 with list z containing a single empty list.

On each loop we create a new list w by looping over z and making each item in w a copy of the corresponding item in z with the current x appended to it. We then extend z with the contents of w.

---

Just for fun, here's an iterative generator that produces subsets (in natural order) from bitstrings. This method is actually quite efficient, and it's good if you want all the subsets of a large sequence without consuming a lot of RAM.

def subsets(seq):
    w = len(seq)
    for i in range(1<<w):
        yield [u for 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]

Bihar

I see what you're saying. Is there any more elegant/pythonic way of doing this? Is slicing expensive? I want to know the best way to do this. Thanks for your explanation! – Undergarment

@YSA: The additional work performed by slicing is work that needs to be done. – Pyrogallol

@Undergarment You could also use the copy module and copy.copy(temp) – Hjerpe

@PM 2Ring can you please explain the iterative solution, I'm having trouble wrapping my mind around it. Explanation for recursion is perfect though. – Undergarment

@Undergarment Does that help? – Bihar

@PM 2Ring yes, thank you very much. Keep spreading the wisdom ! – Undergarment

Answer 2

Variables are references to the actual value. However, since Python lists are mutable, when you change the value through one reference, the other reference will reflect the changes as well.

>>> a = [1, 3]
>>> b = a
>>> b
[1, 3]
>>> b.append(1)
>>> b
[1, 3, 1]
>>> a
[1, 3, 1]

Make a copy of the list before you append it to fix.

def subsets(nums):
    res = []
    backtrack(res, [], nums, 0)
    return res

def backtrack(res, temp, nums, start):
    res.append([])
    for i in temp:
        res[-1].append(i);
    for i in range(start, len(nums)):
        temp.append(nums[i])
        backtrack(res, temp, nums, i + 1)
        temp.pop() # Backtrack

As stated in the other answer, you can use res.append(temp[:]) too.

Hjerpe

Lists are not treated differently from other objects. – Pyrogallol

The fact that the change performed by b.append(1) is visible through a does not mean that lists get any special treatment. You may want to read up on how Python variables and assignment work. – Pyrogallol

@OliverNi Your answer is correct, in as much as the correct output is produced but you are doing your copying in a rather strange way. Then your explanation is a bit sloppy, as to how arrays are "different" than "normal" variables. To some extent I agree with you, but they are really treated exactly like any other object, with mutable fields. – Caitlin

@Caitlin okay. I will edit my answer to make it more clear. – Hjerpe

@Pyrogallol Is that better? – Hjerpe

Yes, that's better. – Pyrogallol