---
# System prepended metadata

title: Leetcode 78. Subsets
tags: [Leetcode]

---

[link](https://leetcode.com/problems/subsets)

---

Given an integer array nums of unique elements, return all possible 
subsets
 (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

#### Example 1:

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

#### Example 2:

Input: nums = [0]
Output: [[],[0]]

#### Constraints:

- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
---

The code defines an inner function, dfs, which performs the depth-first search. The function takes an index, i, as a parameter, indicating the current element to consider.

The base case of the recursion is checked with the condition if i >= len(nums). This condition is true when we have considered all the elements in the list.

Inside the base case, the current subset is appended to the res list using res.append(subset.copy()). Since subset is a mutable object, subset.copy() is used to create a copy of subset and append it to res. This is necessary because we will be modifying subset in the recursive steps, and we want to store different subsets at different stages.

The code proceeds to the recursive steps. First, the current element, nums[i], is added to the subset list using subset.append(nums[i]). The dfs function is recursively called with i + 1, which means the next element in the list will be considered. After the recursive call, subset.pop() is used to remove the last element from the subset list. This step is crucial for backtracking and generating different combinations of elements.

Another recursive call to dfs is made with i + 1 to explore the case where the current element is not included in the subset. The dfs function is initially called with i = 0, starting the recursive process. Finally, the dfs function is called within the subsets method with an initial index of 0. After the DFS process completes, the res list containing all the subsets is returned.

#### Solution 1
```python=
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            
            subset.append(nums[i])
            dfs(i + 1)

            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res
        
```
O(T): O(2^N * N)
O(S): O(2^N * N)