백트래킹(Backtracking) 간단 정리 및 활용

백 트래킹

만족할 때 까지 탐색 후 불만족할 시 되돌아오는 방식

• 정의

  만족할 때 까지 탐색 후 불만족할 시 되돌아오는 방식

• 구현

  DFS 가 백트래킹의 구현 알고리즘

• 기본 코드

    def dfs(args):
  
        # 재귀 종료 코드
        if ():
            return
  
        # 탐색 코드
        # 탐색 대상이 List 인 경우
        # 탐색 대상이 어떤 객체냐에 따라 달라질 수 있음
        for i in range():
            dfs(args)
  
  

• 활용

  • Leetcode 39. Combination Sum

    해당 문제는 탐색 대상인 List 도 정렬되어 있고 조건에 맞는 대상을 고르는 문제라 투 포인터 문제로 잘못 판단할 수도 있음

    선택된 요소가 2개보다 적을 수도 있고 그 이상으로 많을 수도 있어서 backtracking 에 맞는 문제

        def combinationSum(self, candidates, target):
    
          def dfs(nums, target, path):
              # 종료 코드
              # 조건 벗어남
              if target < 0:
                  return
    
              # 종료 코드
              # 조건 만족
              if target == 0:
                  ret.append(path)
                  return
    
              # 탐색 코드
              for i in range(len(nums)):
                  dfs(nums[i:], target-nums[i], path+[nums[i]])
    
          ret = []
          dfs(candidates, target, [])
          return ret
    

    기본 코드에 맞춰서 구현

    하지만 조건 부분에서 최적화 안 됨

    • 최적화

      
      def combinationSum(self, candidates, target):
      
        def dfs(nums, target, path):
            # if target > 0 삭제
            # 불필요 조건 확인 방지
      
            # 종료 코드
            # 조건 만족
            if target == 0:
                ret.append(path)
                return
      
            for i in range(len(nums)):
      
                # 점프 코드
                # 최적화
                if nums[i] > target:
                    break
      
                dfs(nums[i:], target-nums[i], path+[nums[i]])
      
        ret = []
        # 선 정렬
        dfs(sorted(candidates), target, [])
        return ret
      
      

      투 포인터 에서 중복을 넘기는 것 처럼 사용하기 위해 선 정렬

      탐색 코드에서 nums[i] > target 일 경우 break 로 반복 탈출 및 재귀 방지

      if target > 0 없애서 불필요한 조건 비교 삭제