# 78. Subsets — LeetCode(Python)

--

I got you!

# Problem:

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

# Solution:

## Explanation —

We use a backtracking algorithm to solve this problem.

A ** subset** array is maintained and we consider two cases at each step.

So, we iterate through the array in a recursive manner, creating a *decision tree* at each iteration.

The first case is when we add the next number in the array to our ** subset** and the second case is when we don’t.

The ** subset** is modified accordingly and the function is called recursively to go further down in the decision tree.

When we hit the end of a path in the tree, i.e. reach a leaf node, we append a copy of the subset to our result array. A copy is needed because, in Python, this array might get modified in the result array as well even if we modify it outside of it.

Finally, we call this backtracking function and return the result array.

## Time and Space Complexity —

The creation of the decision tree takes the same amount of time as it takes to generate all subsets, which is of the order of O(n * 2^n).

Also, we require a linear amount of extra space to store our subset variable in the recursion stack as we iterate through all elements in the array.

Thus, if *n* is the length of the array *nums,*

Time Complexity: O(n * 2^n)

Space Complexity: O(n)

As we can see, this algorithm is no better than just sorting the coordinates by distance. So, we improve upon this approach in the next part of the solution.