← 전체 회차
a-071-subsets2026-07-27mediumleetcode #78neetcode150

부분집합

#array#backtracking#bit-manipulation
↗ leetcode #78 · a-071-subsets
01

문제

· problem
P.a-071-subsets

부분집합

↗ leetcode #78

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

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

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    부분집합(subset)의 정의가 무엇인가요?
  • ☐
    결과의 순서가 중요한가요?
  • ☐
    각 원소를 여러 번 사용할 수 있나요?
  • ☐
    왜 subset.copy()를 사용하나요? append(subset)으로는 안 되나요?
  • ☐
    시간 복잡도는 얼마나 되나요?
  • ☐
    입력 배열의 원소들이 미리 정렬되어야 하나요?
  • ☐
    중복된 원소가 입력에 포함될 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 리스트 초기화
○
res = []
○
res = [[]]
○
res = set()
step 2· 현재 부분집합 초기화
○
subset = []
○
subset = nums[:]
○
subset = [nums[0]]
step 3· 재귀 종료 조건 확인│ 중첩
○
if i >= len(nums):
○
if i == len(nums) - 1:
○
if i > len(nums):
step 4· 완성된 부분집합 저장│ │ 중첩
○
res.append(subset.copy())
○
res.append(subset)
○
res.append(tuple(subset))
step 5· 현재 원소 포함 및 재귀│ 중첩
○
subset.append(nums[i])
○
subset = subset + [nums[i]]
○
subset.insert(0, nums[i])
step 6· 백트래킹으로 원소 제거│ 중첩
○
subset.pop()
○
subset = subset[:-1]
○
subset.remove(nums[i])
step 7· 재귀 탐색 시작
○
dfs(0)
○
dfs(1)
○
dfs(len(nums) - 1)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

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