Subsets

View Subsets on LeetCode

Statistics

Time Spent Coding
10 minutes

Time Complexity
O(n * 2ⁿ) - 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ⁿ) - 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

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