subsets.py

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

# Note: The solution set must not contain duplicate subsets.

# For example,
# If nums = [1,2,3], a solution is:

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


# O(2**n)


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

def backtrack(res, nums, stack, pos):
    if pos == len(nums):
        res.append(list(stack))
    else:
        # take nums[pos]
        stack.append(nums[pos])
        backtrack(res, nums, stack, pos+1)
        stack.pop()
        # dont take nums[pos]
        backtrack(res, nums, stack, pos+1)


# simplified backtrack

# def backtrack(res, nums, cur, pos):
    # if pos >= len(nums):
        # res.append(cur)
    # else:
        # backtrack(res, nums, cur+[nums[pos]], pos+1)
        # backtrack(res, nums, cur, pos+1)


# Iteratively
def subsets2(self, nums):
    res = [[]]
    for num in sorted(nums):
        res += [item+[num] for item in res]
    return res

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