---
tags: data_structure_python
---

# Subsets <img src="https://img.shields.io/badge/-easy-brightgreen">

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],
  []
]

# Solution

- Time/Space complexity: O(N * 2^N).
- N because we copy the array.
- 2^N because there is 2^N subsets.

### Solution 1: Bit manipulation 1

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        nbOfSubsets, subset = 1 << len(nums), []
        for i in range(nbOfSubsets):
            tmp = []
            for idx, char in enumerate(bin(i)[2:][::-1]):
                if char == "1":
                    tmp.append(nums[idx])
            subset.append(tmp)
        return subset

### Solution 2: Bit manipulation 2

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        nbOfSubsets, subset = 1 << len(nums), []
        for b in range(nbOfSubsets):
            tmp = []
            for i in range(len(nums)):
                if b & 1 << i:
                    tmp.append(nums[i])
            subset.append(tmp)
        return subset

### Solution 3: Cascading


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for num in nums:
            res += [subset + [num] for subset in res]
        return res

### Solution 4: Recursive

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def helper(nums, subset, res, i):
            if i == len(nums):
                res.append(subset[:])
            else:
                helper(nums, subset, res, i+1)
                subset.append(nums[i])
                helper(nums, subset, res, i+1)
                subset.pop()
                
        res = []
        helper(nums, [], res, 0)
        return res