[리트코드] Combination Sum(python)

리트코드, Combination Sum_조합의 합

TL;DR

• 깊이 우선 탐색(DFS)

문제

1. 주어진 구분된 정수 배열 candidates와 목표 정수 target에 대해서 조합한 숫자들의 합이 target이 되는 유일한 조합들의 배열을 반환해야 한다.
2. candidates 내에 동일한 숫자를 여러 번 고를 수 있으며, 만약 적어도 하나의 숫자가 다르다면 두 조합은 다른 조합이다.
3. 문제에서 target이 되는 조합의 수가 150보다 적은 것을 보장한다.

 

- 주어진 정수 배열 candidates 내에 있는 숫자를 중복 선택한 조합들에 대해서 조합의 합이 target이 되는 배열을 반환하면 된다.

입출력 형태

입출력 예시

 

- 주어진 정수 배열 [2, 3, 6, 7]에서 합이 7이 되도록 숫자를 조합하는 경우는 예시에서 확인할 수 있듯이 [2, 2, 3], [7] 두 가지이다.

- 예시에서 주어진 바와 같이 주어진 정수 배열에서 동일한 숫자를 여러 번 선택할 수 있다.

풀이

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        
        if len(candidates) == 1 and candidates[0] > target:
            return answer
        
        def dfs(diff: int, index: int, combinations: List[int]):
            if diff == 0:
                answer.append(combinations)
                return
            if diff < 0:
                return
            
            for i in range(index, len(candidates)):
                dfs(diff - candidates[i], i, combinations + [candidates[i]])
                
        dfs(target, 0, [])
        
        return answer

 

- 재귀 기반의 DFS를 활용하여 문제를 해결하였다.

- DFS는 조합에 있는 숫자들의 합과 target의 차를 나타내는 diff, 조합을 조회할 index, 조합들이 저장될 combinations. 3개의 매개변수를 갖고 있다.

  - diff가 0이 되는 순간 해당 조합은 문제에서 말하는 조건을 만족하므로 정답 배열에 담는다.

  - diff가 0보다 작아지는 순간 해당 조합은 더 이상 조회할 필요가 없으므로 종료한다.

  - candidates를 순회하며, target과 candidates의 원소를 비교, 조합을 만들며 재귀적으로 반복 호출한다.

- candidates의 모든 원소들에 대해 재귀 호출이 반복 수행되며 생성할 수 있는 모든 조합을 만들고, target과의 차를 비교하게 된다. 문제 조건 3번에서 150개 미만의 조합으로 정답을 도출해낼 수 있다는 제약이 걸려있기 때문에 시간 초과 등의 문제 없이 문제를 해결할 수 있다.