interview-questions/arrays-and-strings/subsets.py

# Given a set of distinct integers, nums, return all possible subsets.
# This could be solved with backtrack algorithm.
# Time complexity: O(1). Only list is appended (in Python. Because Python allocates
# up to twice of the space as needed)
# Space complexity: O(n^2). Store all the combination of a list with length n
import pytest

def test_subsets():
    assert subsets([0,1]) == [[],[0],[0,1],[1]]

def subsets(nums):
    def backtrack(list, temp_list, nums,start):
        list.append(temp_list)
        for i in range(start,len(nums)):
            backtrack(list,temp_list+[nums[i]],nums,i+1)
        return list

    list = []
    backtrack(list,[],nums,0)
    return list