78. Subsets (Array, Backtracking, Bit Manipulation)

링크 - https://leetcode.com/problems/subsets/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Cascading

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]

        for num in nums:
            newSubsets = []
            for curr in ans:
                temp = curr.copy()
                temp.append(num)
                newSubsets.append(temp)

            for curr in newSubsets:
                ans.append(curr)

        return ans

Time Complexity: O(N * 2^N)

Space Complexity: O(N * 2^N)

2) Backtracking

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []

        def backtrack(cur_sub, idx):
            ans.append(cur_sub[:])

            for i in range(idx, len(nums)):
                cur_sub.append(nums[i])
                backtrack(cur_sub, i + 1)
                cur_sub.pop()

        backtrack([], 0)
        return ans

Time Complexity: O(N * 2^N)

Space Complexity: O(N)

3) Lexicographic (Binary Sorted) Subsets

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []

        for i in range(2**n, 2**(n+1)):
            # e.g. i = 8 -> bin(i) = 0b1000 -> bin(i)[3:] = 000
            bitmask = bin(i)[3:]

            ans.append([nums[j] for j in range(n) if bitmask[j] == "1"])

        return ans

Time Complexity: O(N * 2^N)

Space Complexity: O(N)