백트랙킹(Permutation)

백트랙킹은 가능성을 탐색하는 방법으로 순열 문제를 풀 때 사용하기 좋다.

 

 

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

from typing import List

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

    def _BT(self, crntNums : List[int]) -> None:
        if len(crntNums) == len(self._nums):
            self._ret.append(crntNums.copy())
            return

        for num in self._nums:
            if num in crntNums:
                continue
            crntNums.append(num)
            self._BT(crntNums)
            crntNums.pop()

    def PermuteUsingHashSet(self, nums:List[int]) -> List[List[int]]:
        self._nums = nums
        self._ret = []
        self._BTUsingHashSet([], set())
        return self._ret

    def _BTUsingHashSet(self, crntNums: List[int], crntSet:set) -> None:
        if len(crntNums) == len(self._nums):
            self._ret.append(crntNums.copy())
            return

        for num in self._nums:
            if num in crntSet:
                continue
            crntNums.append(num)
            crntSet.add(num)
            self._BTUsingHashSet(crntNums, crntSet)
            crntNums.pop()
            crntSet.remove(num)

    
                
perm = Perm()
ret = perm.Permute(nums=[1,2,3])
print(ret)
ret = perm.PermuteUsingHashSet(nums=[1,2,3])
print(ret)

 

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