← 전체 회차
a-074-subsets-ii2026-07-30mediumleetcode #90neetcode150

부분집합 II

#array#backtracking#bit-manipulation
↗ leetcode #90 · a-074-subsets-ii
01

문제

· problem
P.a-074-subsets-ii

부분집합 II

↗ leetcode #90

중복을 포함할 수 있는 정수 배열 nums가 주어질 때, 모든 가능한 부분집합(멱집합)을 반환하세요. 해 집합에는 중복된 부분집합이 포함되어서는 안 됩니다. 답을 어떤 순서로든 반환할 수 있습니다.

제약
  • · 1 ≤ nums.length ≤ 10
  • · -10 ≤ nums[i] ≤ 10
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,2]
[[],[1],[1,2],[1,2,2],[2],[2,2]]
example 2input → output
[0]
[[],[0]]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    배열의 중복된 원소는 결과에서도 중복된 부분집합을 만들어야 하나요?
  • ☐
    결과 부분집합의 순서가 정해져 있나요?
  • ☐
    모든 원소가 같은 경우([1,1,1])에는 몇 개의 부분집합이 반환되나요?
  • ☐
    입력 배열을 수정해도 되나요?
  • ☐
    공집합도 결과에 포함되어야 하나요?
  • ☐
    백트래킹 대신 반복적 방법으로 구현할 수 있나요?
  • ☐
    결과의 부분집합들이 각각 정렬되어야 하나요?
  • ☐
    최대 2^n개의 부분집합 때문에 특별한 최적화가 필요한가요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 리스트 초기화
○
res = []
○
res = set()
○
result = {}
step 2· 배열 정렬 (중복 원소를 인접하게)
○
nums.sort()
○
nums = sorted(nums)
○
# 정렬 스킵
step 3· 기저 사례: 배열 끝에 도달│ │ 중첩
○
if i == len(nums):
○
if i >= len(nums):
○
if len(subset) == len(nums):
step 4· 현재 원소 포함 및 탐색│ │ 중첩
○
subset.append(nums[i])
○
subset.append(nums[i]); backtrack(i, subset)
○
subset.append(nums[i]); backtrack(i + 2, subset)
step 5· 원소 제외 시 중복 건너뛰기│ │ 중첩
○
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
○
if nums[i] == nums[i + 1]: i += 1
○
while nums[i] == nums[i + 1]: i += 1  # 범위 체크 없음
step 6· 제외 경로에서 재귀│ │ 중첩
○
backtrack(i + 1, subset)
○
backtrack(i, subset)
○
backtrack(len(nums), subset)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
3
        res = []
4
        nums.sort()
5
6
        def backtrack(i, subset):
7
            if i == len(nums):
8
                res.append(subset[::])
9
                return
10
11
            # All subsets that include nums[i]
12
            subset.append(nums[i])
13
            backtrack(i + 1, subset)
14
            subset.pop()
15
            # All subsets that don't include nums[i]
16
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
17
                i += 1
18
            backtrack(i + 1, subset)
19
20
        backtrack(0, [])
21
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,2]
→
[[],[1],[1,2],[1,2,2],[2],[2,2]]
case 2
[0]
→
[[],[0]]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.