[DSA][Backtracking] 01. Subsets

LeetCode 78

 

01. Subsets

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.

 

 

[아이디어]

- 각 원소가 포함되는 경우와 포함되지 않는 경우를 나누어 가능한 모든 부분 집합을 탐색한다.

 

 

[풀이 1] Backtracking

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

        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

Backtracking은 탐색을 진행할 때, 각 원소가 포함되는 경우와 포함되지 않는 경우를 나누어 가능한 모든 부분 집합을 탐색하는 방식이다. 이 방법은 재귀적으로 원소를 선택한 후 결과에 추가하거나, 선택을 취소하고 이전 상태로 돌아가는 방식으로 동작한다. 핵심은 pop()을 이용하여 마지막에 추가된 원소를 제거하고, 이를 통해 탐색이 완료된 후 다른 선택을 탐색하는 것이다.

 

 

[풀이 2] Iteration

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

        for num in nums:
            res += [subset + [num] for subset in res]

        return res

위의 재귀 방식 대신, 반복문을 사용하여 동일한 방식으로 문제를 해결할 수 있다. 이 방법은 현재까지 구한 부분 집합에 새로운 원소를 추가하는 방식으로 동작한다. 새로운 원소를 추가한 부분 집합을 기존 부분 집합에 += 연산을 통해 추가하며, 이는 원소를 포함하는 부분 집합과 포함하지 않는 부분 집합을 동시에 만들어낸다.

 

 

[풀이 3] Bit Manipulation

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

비트 조작 방법은 각 원소가 부분 집합에 포함되거나 포함되지 않는 경우를 이진수로 표현하는 방식이다. 배열의 길이가 n이면, 0부터 2ⁿ-1까지의 이진수를 사용하여 각 부분 집합을 나타낼 수 있다. 각 이진수에서 1은 해당 원소가 포함된 경우를, 0은 포함되지 않은 경우를 의미한다. 이를 통해 각 원소가 포함되는지 여부를 빠르게 확인할 수 있다. i & (1 << j)를 사용하면, i의 j번째 비트가 1인 경우에 nums[j]가 포함된 부분 집합을 생성할 수 있다.

 

⏱️ 시간복잡도

각 원소는 포함할지 말지 두 가지 선택지를 가지므로, 가능한 조합의 수는 총 2ⁿ개이다. 각 부분 집합을 생성할 때 최대 n개의 원소를 처리해야 하므로, 전체 시간 복잡도는 O(n × 2ⁿ)이다.

🧠 공간복잡도

모든 가능한 부분 집합을 저장해야 하므로, 결과적으로 2ⁿ개의 부분 집합이 생성된다. 따라서 전체 공간 복잡도는 O(2ⁿ)이다.