Backtracking: 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