---
# System prepended metadata

title: 'Subsets <img src="https://img.shields.io/badge/-easy-brightgreen">'
tags: [data_structure_python]

---

---
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

```python=
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

```python=
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

![](https://i.imgur.com/bWzlRdh.png)


```python=
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 

```python=
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
```