p.351 36번 조합의 합

[DoTheBestMayB]

입력이 오름차순으로 주어질 때, 재귀 호출하는 for 문에서 candidates[i]의 값이 계속 증가하거나 같음이 보장되므로

종료 조건 ( csum < 0 )을 재귀 호출하는 for 문에 사용해서 불필요한 반복을 피하면 실행 시간이 단축된다고 생각합니다.
리트코드에서 주어지는 입력값은 정렬되어 있지 않기 때문에 candidates를 sort 하고 나서 사용했습니다.

문제에서 입력 원소 개수가 200개라서 현재 큰 차이는 없지만, 매우 커진다면 유의미한 차이가 생길 것 같습니다.

ex) 현재 csum = 3 이고, for문에서 이후 주어지는 값이 [4,4,4,4,4,4,4,4, ,,,,,,,, 4] 가 주어졌을 때

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        
        def dfs(csum, index, path):
            if csum == 0:
                result.append(path)
                return
            
            for i in range(index, len(candidates)):
                # 종료 조건을 for 문 안 쪽으로 변경했습니다.
                if csum - candidates[i] < 0:
                    break
                dfs(csum - candidates[i], i, path + [candidates[i]])
        
        # 입력 값을 사용하기 전에 정렬해줬습니다.
        candidates.sort()
        dfs(target, 0, [])
        return result

[likejazz]

매우 효율적인 풀이네요. 깃헙에 효율적인 풀이로 추가하도록 하겠습니다. 감사합니다.