[LeetCode/Python] 39. 조합의 합(Combination Sum)

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라.

 

각 원소는 중복으로 나열 가능하다.

 

Example:

 

Input: candidates = [2,3,6,7], target = 7

 

Output: [[2,2,3], [7]]

 

 

 

1. 내가 직접 푼 코드

 

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        output = []
 
        def dfs(stack, hap):
            if hap == target:
                output.append(stack)
            elif hap > target:
                return
            for candidate in candidates:
                dfs(stack + [candidate], hap + candidate)
 
        dfs([], 0)
        
        outputs = []
        for val in output:
            a = sorted(val)
            if a not in outputs:
                outputs.append(a)
        return outputs
 

 

해설:

 

재귀 함수로 dfs를 구현했다.

 

속도는 하위 5%로 엄청 허접하게 나왔다!

 

dfs 함수를 통해 합이 target 값이 나올 때까지 오지게 굴렸고

 

이렇게 되면 문제점이 뭐냐면

 

[2,2,3]과 [3,2,2], [2,3,2]가 모두 output에 들어간다.

 

겹치는 건 없애줘야 돼서 sort를 시켜서 비교를 통해 최종 출력 outputs를 리턴한다.

 

 

 

** 깔끔한 코드 **

 

2. DFS로 중복 조합 그래프 탐색

 

 

class Solution:
    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
 

 

해설:

 

내 생각에 이 코드가 1번 코드보다 속도 면에서 빨랐던 이유는 index라는 변수를 통해 접근해서 그런 것 같다.

 

나 같은 경우 슬라이싱을 통해 candidates를 잘라가며 처리했는데 그럴 경우 속도는 1번 코드와 별 차이가 없다.