### View *Subsets* on LeetCode

## Statistics

**Time Spent Coding**

10 minutes

**Time Complexity**

O(n * 2^{n}) - This formula represents the number of combinations able to be made out of a list with a length of n.

**Space Complexity**

O(n * 2^{n}) - Since this algorithm is reccursive the program requires the same amount in space complexity to store all the reccursive calls.

**Runtime Beats**

99.93% of other submissions

**Memory Beats**

77.64% of other sumbissions

## Explanation

Comments explain the program.

## Algorithm Used

**Backtracking -** An algorithmic technique that incrementally builds possible solutions by exploring all possible paths at each increment.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
def __init__(self):
# Initialize the output list with an empty set
self.output = [[]]
def helper(self,root,nums):
# Since the nums list is sorted no duplicates will be added
# Always add the root list
self.output.append(root)
for i,n in enumerate(nums):
# Create a copy of the root list
tmp = root[::-1]
tmp = tmp[::-1]
# Add the current iteration to the list
tmp.append(n)
# Similar to the initial call of the helper function
self.helper(tmp, nums[i+1:])
def subsets(self, nums: List[int]) -> List[List[int]]:
# Sorting the input list allows easier mutation of the
# list to avoid duplicate combinations
nums.sort()
# For each number n, explore its possible combinations
for i,n in enumerate(nums):
# Since the list is sorted we only need to explore the right half
# of the list, past the current number
# Since the subsets are represented as lists, turn n into a list
self.helper([n],nums[i+1:])
return self.output