[DSA][Backtracking] 05. Subsets II

LeetCode 90

 

05. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

 

 

[아이디어]

- 각 원소가 포함되는 경우와 포함되지 않는 경우를 나누어 가능한 모든 부분 집합을 탐색하고, 같은 level에서 중복된 숫자가 있으면 PASS 한다.

 

 

[풀이 1] Backtracking

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

        def dfs(i):
            if i == len(nums):
                res.append(subset[::])
                return

            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()

            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            dfs(i + 1)

        dfs(0)
        return res

Subset II는 이전 Subset과 비교했을 때 입력 배열에 중복 값이 존재할 수 있다는 차이가 있다. 2025.11.08 - [자료구조와 알고리즘] - [DSA][Backtracking] 01. Subsets

Combination Sum 문제(2025.11.10 - [자료구조와 알고리즘] - [DSA][Backtracking] 02. Combination Sum)에서 Combination Sum II 문제(2025.11.14 - [자료구조와 알고리즘] - [DSA][Backtracking] 03. Combination Sum II)로 넘어갈 때 문제 조건이 동일하게 변경된 것을 참고하여 Subset  II에도 동일한 로직을 추가해 주면 된다.

nums에 같은 값이 여러 개 있으면, 다른 인덱스의 같은 숫자를 선택해도 동일한 조합이 여러 번 만들어질 수 있다. nums = [1, 1, 2]라면 첫 번째 1과 2를 택해도 두 번째 1과 2를 택해도 subset= [1, 2]가 만들어지므로 중복된 리스트가 답에 포함된다.

DFS에서는 각 재귀 호출이 "같은 깊이(level)"에서 선택을 결정하는데, 같은 level 내에서 이미 사용한 숫자가 다시 나오면 이를 skip 한다. 기존에는 nums[i]를 추가하고, backtrack을 한 후에 해당 원소를 pop 하고 다시 backtrack을 했다면 (해당 원소를 선택하고 이후 동작 & 빼고 이후 동작) 중복된 숫자를 배제하기 위해 지금 원소와 다음 원소가 같다면 모두 pass 해주는 것이다.

 

⏱️ 시간복잡도

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

🧠 공간복잡도

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