LeetCode 78: Subsets

Take or skip: Recursion

We skip or take each element.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def collect(self, i, nums, curr, subsets):
        if i == len(nums):
            subsets.append(curr[:])
            return
        
        self.collect(i+1, nums, curr, subsets)

        curr.append(nums[i])
        self.collect(i+1, nums, curr, subsets)
        curr.pop()

    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        self.collect(0, nums, [], subsets)

        return subsets

Take or skip: Iterative

Say we have subsets with (n-1) elements. For the n-th element, we can take it or we can skip it. Skipping n-th element is same as keeping the subsets with only (n-1) elements or the subsets we already have. Taking n-th element means we add n-th element to each of the previous subsets.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = [[]]
        for x in nums:
            m = len(subsets)
            for i in range(m):
                subsets.append( subsets[i]+[x] )

        return subsets

Bitwise

For $n$ elements there are $2^n$ subsets. From the 1-bits in the numbers from $0$ to $2^n-1$ we decide which elements to include in a subset.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def get_subset(self, x, nums):
        subset = []
        for i in range(len(nums)):
            if x & 1:
                subset.append(nums[i])
            x >>= 1
 
        return subset
 
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        max = (1 << len(nums))-1
        for x in range(max+1):
            subsets.append(self.get_subset(x, nums))
         
        return subsets

unreasonably effective