백트랙킹(Subsets)

문제: nums로 주어진 숫자로 만들수 있는 subsets들을 return하여라

 

이를 recursive 한 방법으로 풀면 아래 그림과 같다

주의 해야할 점

  1. letters를 넘길 때 reference로 넘기면 쓸데없는 deep copy를 막을 수 있다.

  2. reference로 넘기면 다음 bt전에 letters를 원복시켜야 한다.

 

from typing import List

class Subsets:
    def GetSubSets(self, nums:List[int]) -> List[List[int]]:
        self._nums = nums
        self._ret = []
        self._BT(0, [])
        return self._ret

    def _BT(self, level:int, subsets:List[int]) -> None:
        if level == len(self._nums):
            self._ret.append(subsets.copy())
            return
        
        crntNum = self._nums[level]
        subsets.append(crntNum)
        self._BT(level + 1, subsets)
        subsets.pop()
        self._BT(level + 1, subsets)

subsets = Subsets()
print(subsets.GetSubSets(nums=[1,2,3]))

 

recursive 방법은 call stack overflow가 발생할 수 있다. 이를 iterative 방법으로 바꾸면 아래와 같다.

(letters를 value로 넘긴다고 가정)

 

 

출처 : (5) 코딩테스트, 초급, Subsets - YouTube