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

Viewed 5567

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)
2 Answers
Related