백트래킹

다이나믹 프로그래밍은 problem을 sub problem으로 나누고, 중복 되는 problem을 memoization하여 

문제를 푸는 방식이다.

 

백트래킹은 decision space 공간을 정의하고 탐색한 뒤 다시, 정의한 공간으로 돌아오는 문제 풀이 방식이다.

 

key pad 문제를 풀어보자.

각 번호에 해당하는 알파벳을 조합하여 모든 경우의 수를 찾는 문제다.

from typing import List

class LetterCombinations:
    def Solutions(self, digits: str) -> List[str]:
        self._keypad = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        self._ret = []
        self._digits = digits

        self._BT(0, [])

        return self._ret

    def _BT(self, digitIdx:int, combList : List[str]) -> None:
        if digitIdx >= len(self._digits):
            combStr = ''.join(combList) 
            self._ret.append(combStr)
            return

        numOfStr = int(self._digits[digitIdx])
        strOfNum = self._keypad[numOfStr]

        for c in strOfNum:
            combList.append(c)
            self._BT(digitIdx + 1, combList)
            combList.pop()


letterComb = LetterCombinations()
print(letterComb.Solutions(digits='259'))

 

출처 : (5) 코딩테스트, 기초, 백트래킹 backtracking 소개 - YouTube