Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:


Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Complete search

Starter code: class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:

	def subsets(self, nums):
		subsets = [[]]
		for v in nums:
			extra = []
			for s in subsets:
				extra.append(s + [v])
			subsets += extra
		return subsets


class Solution:

	def subsets(self, nums):

		def mask(x):
			return 1 << x
		exp = 1 << len(nums)
		ans = []
		for count in range(exp):
			new = []
			i = 0
			while mask(i) <= count:
				if mask(i) & count:
					new.append(nums[i])
				i += 1
			ans.append(new)
		return ans


class Solution:

	def subsets(self, nums):
		result = [[]]
		for num in nums:
			result += self.get_subset(result, num)
		return result

	def get_subset(self, subsets, item):
		new_subset_with_item = []
		for subset in subsets:
			new_subset_with_item.append(subset + [item])
		return new_subset_with_item