[파이썬 알고리즘 인터뷰][그래프] 조합의 합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

숫자 집합을 중복 포함 조합하여 합이 target이 되는 원소들 나열

 

책에서 구현된 코드

def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
    result = []
    
    def dfs(csum, index, path):
        if csum < 0:
            return
        if csum == 0:
            result.append(path)
            return
            
        for i in range(index, len(candidates)):
            dfs(csum - candidates[i], i , path + [candidates[i]])
            
    dfs(target, 0, [])
    return result

 

기억해야할 기법

• 중복되는 숫자가 없는 배열의 조합을 구할 때, 재귀시 현재 index부터 탐색
  
  • 중복되는 값이 없으므로, 중복된 조합 검사가 필요 없음
  • sorting이 필요 없음

 

내가 구현한 코드

def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        nums = sorted([n for n in candidates if n <= target], reverse=True)
        result = []

        def get_sum(elts: list, sum: int, s: int):
            if sum == target:
                tmp_res = sorted(elts[:])
                if tmp_res not in result:
                    result.append(tmp_res)
                return

            for i in range(s, len(nums)):
                num = nums[i]
                if sum + num <= target:
                    elts.append(num)
                    get_sum(elts, sum+num, s)
                    elts.pop()

        get_sum([], 0, 0)
        return result

• 재귀할 때 검사 시작 인덱스를 바꾸려고 파라미터를 넣고서, 그 값을 그대로 넣었다
  • 처음부터 검사해서 정답은 나왔는데, 속도 차이가 컸다
  • 원인을 찾으려고 이것저것 해보았다
• 중복검사가 필요할 줄 알고, dict로 검사를 넣었는데 필요가 없었다
  • 중복검사를 추가해도 dict라 그런지 속도차이는 거의 없었다