부분집합과 멱집합
백트래킹과 비트 마스킹으로 집합의 모든 부분집합을 생성하고, 정렬한 뒤 중복 원소를 건너뛰어 중복을 처리합니다.
부분집합과 멱집합은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
부분집합과 멱집합
집합 S의 멱집합은 the 공집합과 S 자체를 포함한 S의 가능한 모든 부분집합의 모음입니다. n개의 원소를 가진 집합에는 정확히 2ⁿ개의 부분집합이 있습니다. [1, 2, 3]의 8개 부분집합은 다음과 같습니다. [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. 이는 가능한 모든 조합, 분할 또는 선택을 찾는 면접 문제에 등장하는 기본적인 조합 문제입니다.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16백트래킹으로 부분집합 생성
선택-탐색-선택 취소 템플릿을 사용합니다. 핵심 설계 결정은 각 재귀 호출에서 현재 부분 경로를 더 많은 원소를 선택하기 전에 즉시 결과에 추가하는 것입니다. 이렇게 하면 빈 상태, 부분 상태, 완성 상태를 포함한 모든 상태가 유효한 부분집합으로 저장됩니다. start 인덱스를 마지막으로 선택한 원소의 오른쪽에 있는 원소만 고려하도록 이동하면 중복을 방지하고 순서를 유지할 수 있습니다.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]비트 마스킹 방식
백트래킹의 대안은 비트 마스킹입니다. 각 부분집합은 n비트 숫자 하나에 대응하며, 비트 i가 1이면 원소 i가 포함되었다는 뜻입니다. 0부터 2ⁿ - 1까지 순회하고 각 숫자에서 비트를 추출해 부분집합을 만듭니다. 이 방식은 반복적이고 실제로 더 빠른 경우가 많으며 코딩하기도 매우 쉽습니다. 하지만 합계 제한과 같은 제약 조건이 있는 문제로는 깔끔하게 일반화되지 않습니다.
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differ반복 방식의 부분집합 생성
반복 방식은 원소를 하나씩 추가하면서 멱집합을 만들어 갑니다. [[] ](공집합)으로 시작합니다. 새로운 원소마다 기존 부분집합을 모두 복제하고, 각 복제본에 새 원소를 추가합니다. n개의 원소를 처리하면 결과에는 2ⁿ개의 모든 부분집합이 들어 있습니다. 이는 비트 마스킹과 동등하지만 비트 단위 연산에 익숙하지 않은 사람에게 더 읽기 쉽습니다.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]부분집합 II: 중복 처리
입력에 중복 원소가 있으면 단순한 방식은 중복된 부분집합을 생성합니다. [1, 2, 2]에서는 2가 두 번 등장하므로 두 경우가 각각 [1, 2]를 독립적으로 생성합니다. 해결 방법은 먼저 배열을 정렬한 다음, 현재 단계에서 후보가 이전 후보와 같으면 건너뛰는 것입니다. 구체적으로 반복문에서 다음을 사용합니다. if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsets중복 값을 건너뛰는 방식이 작동하는 이유
i > start and nums[i] == nums[i-1] 조건은 같은 재귀 수준(같은 start)에서만 중복 값을 건너뜁니다. 서로 다른 깊이에서 같은 값을 선택하는 것은 막지 않습니다. [1, 2, 2]의 경우 수준 0에서 첫 번째 2(인덱스 1)를 포함한 다음, 다음 수준(start=2)에서 두 번째 2를 포함하여 [2, 2]를 만듭니다. 하지만 수준 0에서 두 번째 2를 다시 포함하려고 하면 이 조건이 이를 감지하여 건너뜁니다.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6고정 크기 부분집합(k-조합)
정확히 크기가 k인 부분집합만 생성하려면(LeetCode 77: 조합) 조기 종료 조건을 추가해야 합니다. 남은 원소로 경로를 크기 k까지 채울 수 없다면 가지치기합니다. 가지치기 조건은 i > n - (k - len(path))입니다. 남은 원소가 충분하지 않으면 일찍 중단합니다. 모든 부분집합을 생성한 후 필터링하는 방식과 비교하면 탐색 공간이 크게 줄어듭니다.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120멱집합의 활용
멱집합 패턴은 다양한 면접 문제 변형에 등장합니다. (1) 두 개의 동일한 크기 부분집합으로 분할 — 어떤 부분집합의 합이 전체 합의 절반인지 확인합니다. (2) 두 부분집합의 최댓값 XOR — 모든 부분집합 쌍을 시도합니다. (3) k개 항목을 선택하는 최소 비용 — k개 원소로 이루어진 부분집합을 열거합니다. 직접 열거하면 지수 시간이 걸리지만, 구조를 파악하면 이 문제 중 상당수는 DP로 해결할 수 있습니다. 멱집합 관점은 최적화할 때에도 상태 공간을 파악하는 데 도움이 됩니다.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20부분집합 합 확인
부분집합 합은 배열의 어떤 부분집합의 합이 목표값과 같은지 묻는 문제입니다. 백트래킹(지수 시간)이나 DP(다항 시간)로 해결할 수 있습니다. 백트래킹 방식은 간단하지만 입력이 크면 실용적이지 않습니다. DP 방식(불리언 테이블 dp[target+1])은 면접에서 선호되는 접근입니다. 두 방식을 모두 이해하면 절충점을 설명하는 데 도움이 됩니다. 백트래킹은 모든 해를 제공하고, DP는 판정 문제에 효율적으로 답합니다.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # True부분집합 열거의 복잡도
모든 부분집합을 생성하려면 O(n × 2ⁿ)의 시간 복잡도를 피할 수 없습니다. 평균 크기가 n/2인 부분집합 2ⁿ개를 생성해야 하기 때문입니다. 모든 부분집합을 요청하는 경우 이보다 나은 알고리즘은 없습니다. 특정 속성을 가진 부분집합 하나만 찾는 문제(예: 최댓값 합을 찾는 문제)라면 DP나 그리디 방식을 우선해야 합니다. 중요한 면접 관점은 모든 부분집합을 열거해야 하는지, 아니면 조건을 만족하는 부분집합이 하나라도 있는지만 확인하면 되는지 항상 묻는 것입니다. 이 답에 따라 지수 시간이나 다항 시간이 허용되는지가 결정됩니다.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')세 가지 접근 방식 비교
모든 부분집합을 생성할 때 백트래킹은 가장 일반적으로 적용할 수 있는 방식으로, 중복 값과 제약 조건에 쉽게 대응합니다. 비트 마스킹은 간결하고 빠르지만 n ≤ 30(정수 크기)으로 제한됩니다. 반복 방식은 직관적이고 재귀 오버헤드를 피할 수 있습니다. 세 방식 모두 O(n × 2ⁿ)의 출력을 생성합니다. 면접에서는 백트래킹을 통해 재귀적 의사 결정 과정을 이해하고 있음을 보여 줄 수 있으며, 이는 더 어려운 문제에도 일반화할 수 있습니다. 접근 방식을 논의할 때 세 가지를 모두 언급하십시오.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8빠른 확인
이번 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
학습 내용 복습
이번 학습에서 다음을 배웠습니다. 백트래킹은 더 탐색하기 전에 각 부분 경로를 결과에 추가하여 모든 부분집합을 생성합니다. 중복 값은 정렬한 다음 같은 재귀 깊이에서 i > start and nums[i] == nums[i-1] 조건으로 반복되는 값을 건너뛰어 처리합니다. 또한 비트 마스킹은 각 부분집합을 고유한 비트 마스크에 대응시키는 간결한 반복 방식의 대안을 제공합니다. 다음에는 서로 관련 있지만 제약 조건이 다른 열거 문제인 순열과 조합을 다룹니다.
자주 묻는 질문
“부분집합과 멱집합” 강의는 무료인가요?
네 — “부분집합과 멱집합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“부분집합과 멱집합”에서 뭘 배우나요?
백트래킹과 비트 마스킹으로 집합의 모든 부분집합을 생성하고, 정렬한 뒤 중복 원소를 건너뛰어 중복을 처리합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“부분집합과 멱집합” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.