[Backtracking: Subset 부분집합] 78. Subsets

78. Subsets

 

https://youtu.be/REOH22Xwdkk?si=J1EDs8ppnu7DJndK

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # subset 만들기
        res = []

        subset = []
        def dfs(idx):
            if idx >= len(nums):
                print(idx, subset)
                res.append(subset.copy())
                return 

            # decision to include nums[idx]
            subset.append(nums[idx])
            dfs(idx + 1)

            # decision to NOT include nums[idx]
            subset.pop()
            dfs(idx + 1)

        dfs(0)

        return res

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(subset, idx):
            # 기저 조건: 모든 요소를 다 탐색했을 때 현재 subset을 결과에 추가
            if idx >= len(nums):
                res.append(subset.copy())
                return

            # 현재 요소를 포함하는 경우 include with nums[idx]
            subset.append(nums[idx])
            dfs(subset, idx + 1)  # 다음 요소로 진행

            # 현재 요소를 포함하지 않는 경우, NOT include with nums[idx]
            subset.pop()  # 상태 복구
            dfs(subset, idx + 1)  # 다음 요소로 진행

        # 빈 subset으로 탐색 시작
        dfs([], 0)
        return res

 

최종 코드

 

이 문제는 "부분 집합(Subset)" 을 모두 구하는 전형적인 백트래킹 (또는 DFS) 문제입니다.
입력 배열 nums에서 가능한 모든 조합(순서 상관없이)을 만들어야 해요.

---

✅ 풀이 방법 요약

• 백트래킹: 각 숫자를 "고르거나 안 고르거나" 두 가지 선택으로 나누어서 모든 경우 탐색
• 재귀 함수를 통해 현재까지의 선택(path)을 쌓아가며 결과(res)에 저장
• 중복이 없고, 원소도 유니크하므로 중복 체크는 안 해도 됨

✅ 동작 과정 (nums = [1,2,3])

• 빈 집합 []
• 1 선택 → [1], → [1,2], → [1,2,3], [1,3]
• 2만 선택 → [2], [2,3]
• 3만 선택 → [3]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(start, path):
            res.append(path.copy()) # 현재 부분집합 저장

            for i in range(start, len(nums)):
                path.append(nums[i]) # 현재 원소 선택
                backtrack(i+1, path) # 다음 원소로 재귀
                path.pop() # backtracking

        backtrack(0, [])
        return res

 

최종 코드

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset, curset = [], []

        def help(i, Nums, SubSet, CurSet):
            if i >= len(Nums):
                SubSet.append(CurSet.copy())
                # 기저 조건(끝까지 도달했을 때) 일때는 subset 에 추가하고
                # 나가기.
                return

            # nums[i] 추가해서 i+1을 subset에 넣기
            CurSet.append(Nums[i])
            help(i+1, Nums, SubSet, CurSet)

            # nums[i] 제외하고 i+1을 subset에 넣기
            CurSet.pop()
            help(i+1, Nums, SubSet, CurSet)

        help(0, nums, subset, curset)
        return subset