Subsets 부분집합

✅ 부분집합이란?

• Set A가 Set B의 부분집합이라는 것은 → A에 있는 모든 원소가 B에도 있어야 함.
• 기호로는 A ⊆ B 로 씀.

---

📌 중요한 성질

1. 모든 집합은 자기 자신의 부분집합이다.
   예: A ⊆ A
2. **공집합(∅)**은 모든 집합의 부분집합이다.
   예: ∅ ⊆ A (어떤 A라도)
3. 원소의 순서는 중요하지 않음.
   예: {1,2,3}과 {3,1,2}는 같은 집합.
4. 원소는 중복될 수 없음.
   예: {1,1,2}는 {1,2}와 같은 집합으로 본다.

---

✔ 예시 복습

• A = {1,2,3,4,5}, B = {5,2,1} → ✅ B는 A의 부분집합
• B = {2,5,1} → ✅ 여전히 부분집합 (순서 상관 없음)
• C = {9,10,11,12}, D = {6,9,10} → ❌ D는 C의 부분집합 아님 (6이 C에 없음)

✅ 부분집합이란?

n개의 원소를 가진 집합의 부분집합 개수는 총 2ⁿ개예요.

 

A = [1, 2, 3] 의 모든 부분집합을 하나하나 적고, 각 단계별로 설명도 붙여드릴게요 😊

---

✅ 원소 수: 3개 → 부분집합 수: 2³ = 8개

---

📋 부분집합 목록 + 설명

번호	부분집합	설명
1	[]	✅ 공집합 (아무것도 고르지 않음)
2	[1]	1만 고른 경우
3	[2]	2만 고른 경우
4	[3]	3만 고른 경우
5	[1, 2]	1과 2를 고른 경우
6	[1, 3]	1과 3을 고른 경우
7	[2, 3]	2와 3을 고른 경우
8	[1, 2, 3]	전체 원소 다 고른 경우 (자기 자신도 포함됨)

※ 공집합 [ ] 도 포함!!

---

🔁 순서는 중요하지 않아요!

예: [1, 2]와 [2, 1]은 같은 부분집합으로 봅니다. → 중복 없이, 정렬 순서만 보면 됨

 

# Time: O(n * 2^n), Space: O(n)
def subsetsWithoutDuplicates(nums):
    # 부분집합들을 저장할 리스트와 현재까지 선택한 원소들을 저장할 리스트 선언
    subsets, curSet = [], []

    # 재귀적으로 부분집합을 생성하는 함수 호출 (i=0부터 시작)
    helper(0, nums, curSet, subsets)
    
    # 최종적으로 만들어진 모든 부분집합 반환
    return subsets

def helper(i, nums, curSet, subsets):
    # i가 nums의 길이 이상이면 재귀 종료 조건에 해당
    if i >= len(nums):
        # 현재까지 만든 부분집합(curSet)을 복사해서 결과 리스트에 추가
        subsets.append(curSet.copy())
        return
    
    # decision to include nums[i]
    # 현재 원소 nums[i]를 부분집합에 포함시키기로 결정
    curSet.append(nums[i])
    helper(i + 1, nums, curSet, subsets)  # 다음 인덱스로 재귀 호출
    curSet.pop()  # 백트래킹: 포함했던 원소를 제거하고 이전 상태로 복귀

    # decision NOT to include nums[i]
    # 현재 원소 nums[i]를 부분집합에 포함시키지 않기로 결정
    helper(i + 1, nums, curSet, subsets)  # 다음 인덱스로 재귀 호출

 

# Time: O(n * 2^n), Space: O(n)
def subsetsWithDuplicates(nums):
    # 중복 제거를 위해 입력 배열을 정렬함 (중복된 값이 인접하게 배치됨)
    nums.sort()

    # 부분집합들을 저장할 리스트와 현재까지 선택한 원소들을 저장할 리스트 선언
    subsets, curSet = [], []

    # 재귀적으로 부분집합을 생성하는 함수 호출
    helper2(0, nums, curSet, subsets)
    
    # 중복을 제거한 최종 부분집합 반환
    return subsets

def helper2(i, nums, curSet, subsets):
    # 모든 원소를 다 확인했으면 종료 조건에 해당
    if i >= len(nums):
        # 현재까지 만든 부분집합(curSet)을 복사해서 결과 리스트에 추가
        subsets.append(curSet.copy())
        return
    
    # decision to include nums[i]
    # 현재 원소 nums[i]를 부분집합에 포함시키기로 결정
    curSet.append(nums[i])
    helper2(i + 1, nums, curSet, subsets)  # 다음 인덱스로 재귀 호출
    curSet.pop()  # 백트래킹: 포함했던 원소를 제거하고 이전 상태로 복귀

    # decision NOT to include nums[i]
    # 현재 원소를 포함하지 않고 건너뛰기로 결정
    # 중복된 값을 여러 번 포함하지 않기 위해, 동일한 값이 연속되면 다음으로 넘김
    while i + 1 < len(nums) and nums[i] == nums[i + 1]:
        i += 1
    helper2(i + 1, nums, curSet, subsets)  # 다음 인덱스로 재귀 호출