Finding all subsets of a list of positive integers using backtracking

[Andrew1235]

The following Python 3 code is provided as the solution to this problem (https://leetcode.com/problems/subsets/solution/) that asks to find all subsets of a list of integers. For example, for the list below the output is [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].

I am not familiar with backtracking. Can someone explain how the code works?

alist = [1,2,3]

ans = []

def backtrack(nums, start, curr):

ans.append(curr)

for i in range(start, len(nums)):

backtrack(nums, i+1, curr + [nums])

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

print(subsets(alist))

 

[Ibix]

The following Python 3 code is provided as the solution to this problem (https://leetcode.com/problems/subsets/solution/) that asks to find all subsets of a list of integers. For example, for the list below the output is [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].

I am not familiar with backtracking. Can someone explain how the code works?

alist = [1,2,3]

ans = []

def backtrack(nums, start, curr):
 
    ans.append(curr) 
    
    for i in range(start, len(nums)):
 
        backtrack(nums, i+1, curr + [nums[i]])

def subsets(nums):     
    backtrack(nums, 0, [])
    return ans
   
print(subsets(alist))

You need to put [code=python] before your code and [/code] afterwards if you want it to be readable.

alist = [1,2,3]
ans = []

def backtrack(nums, start, curr): 
    ans.append(curr)     
    for i in range(start, len(nums)): 
        backtrack(nums, i+1, curr + [nums[i]])

def subsets(nums):     
    backtrack(nums, 0, [])
    return ans
   
print(subsets(alist))

 

[pbuk]

I am not familiar with backtracking. Can someone explain how the code works?

The best (only?) way to understand it is to work through it line by line. You can do this on paper, or by inserting print statements in the code, or by using the 'watch' facitilty of an IDE and stepping through the code.

 

[Ibix]

What pbuk said. At the very least, adding

print("backtrack called with)
print(" nums =",nums)
print(" start =",start)
print(" curr =",curr)

to the beginning of the backtrack function will show you how it's working through the data. First run it with a two element list, then a three element list, etcetera.

 

[sysprog]

You might gain some further insight from looking at https://rosettacode.org/wiki/Power_set#Python.