Leetcode 39

Combination of Sum

dfs를 사용한 풀이

언어: python3

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        end = len(candidates)
        result = []
        candidates = sorted(candidates)
    
        def dfs(start:int,cur:List[int],remain:int):
            
            if remain ==0:
                result.append(cur[:])
                return
                
            if remain < candidates[start]:
                return
            
            for i in range(start,end):
                if target >= candidates[i]:
                    cur.append(candidates[i])
                    dfs(i,cur,remain-candidates[i])
                    cur.pop()
        dfs(0,[],target)            
                    
        return result

• 풀이 설명
• 풀이는 정렬된 candidates 배열을 가정하기 때문에 먼저 오름차순 정렬 dfs 라는 중첩함수를 정의하고 바닥조건 두가지를 설정
  remain이 정확한 합에 이를 경우에만 재귀를 종료할 수 있도록 설정