leetcode.com 39. Combination Sum

 문제 링크: https://leetcode.com/problems/combination-sum/description/

파이썬 소스: https://bit.ly/4aK4DGk

 

 다이나믹 프로그래밍(DP)을 사용해서 풀이를 할 수도 있고, 백트랙킹(backtracking)으로 문제를 풀이할 수도 있습니다. 상대적으로 코딩할 양이적은 백트랙킹으로 문제를 풀어보겠습니다.

 

재귀함수(recursive function)에 꼭 넘겨줘야 할 변수부터 알아보겠습니다.

 

candidates: 이 리스트를 넘겨줘야, 리스트 안에서 하나씩 숫자를 꺼낼 수 있습니다.

target 값을 넘겨줘야, 리스트 안에 있는 숫자의 합이 target과 같은 지 비교할 수 있겠죠.

pathes: 재귀함수를 한번씩 호출하면서, candidates에 있는 숫자 중에 한 개씩 꺼내서, 넣어줄 리스트입니다.

sm: sum의 약자로 sm이라고 했습니다. pathes에 들어 있는 모든 원소의 합입니다. 매번 리스트의 합을 계산하면 속도가 좀 느려질 수 있어서, 별도의 변수 sm으로 합을 전달합니다.

output: pathes리스트의 모든 원소의 합이 target과 같으면, output에 넣어서, combinationSum()메서드가 리턴 할 때, output 변수를 답으로 리턴합니다.

 

위의 5개의 변수를 가지고 구현을 해서 문제를 풀면, 아래와 같은 중복된 값이 발생합니다.

Example 1번을 예로 들어보면, 아래와 같은 중복이 발생한다는 의미입니다.

[2,2,3], [2,3,2] 이 두개의 리스트는 이 문제에서는 서로 같은 답으로 취급해야 하기에, 이런 중복을 처리하는 방법이 필요합니다.

애초에 이런 중복이 발생하지 않도록 이문제를 풀 수 있는 방법은 없을까요?

그렇게 하려면, candidates를 정렬해서, 작은 숫자가 앞에 오도록 해야 합니다.

재귀함수를 호출할수록, candidates를 가리키는 인덱스 같은 위치를 가리키거나, 뒤로 이동하도록 하면 위와 같은 리스트 중복을 피해서 답을 구할 수 있습니다.

Example 1번을 예로 들면,

첫번째 재귀함수 호출에서 2를 선택

두번째 재귀함수 호출에서 2를 선택 / 인덱스가 같은 위치를 가리킨 것이죠

세번째 재귀함수 호출에서 2를 선택 / 인덱스가 같은 위치를 가리킨 것입니다.

네번째 재귀함수 호출에서 가장작은 숫자인 2를 선택하지만, 합이 8 > target 7 보다 큽니다.

다시 세번째 재귀함수 호출에서, 3을 선택 / 합이 7이 되어서, output에 [2, 2, 3]을 넣습니다.

세번째 재귀함수 호출이 끝나고, 두번째 재귀함수로 리턴합니다.

두번째 재귀함수 호출에서 3을 선택합니다. / 인덱스가 1증가합니다. [2, 3]이 pathes에 들어 있습니다.

다시 세번째 재귀함수 호출에서, 3을 선택 / 인덱스가 같은 위치의 candidates를 가리키거나, 더 큰 인덱스만 가리킬 수 있습니다. 따라서, 2 + 3 + 3 = 8 > target 7 보다 크게 됩니다.

 

따라서, idx_begin 변수, 즉, candidates에서 처음 가지고 올 숫자를 가리키는 변수가 한 개 더 필요합니다.

 

위의 문제 풀이 방법에 따라서 구현하면 아래와 같이 구현할 수 있습니다.

from typing import List class Solution:     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:         output = []         candidates.sort()         self.rec(candidates, 0, target, [], 0, output)         return output     def rec(self, candidates: List, idx_begin, target, pathes: List, sm, output: List):         if target == sm:             output.append(pathes)             return         for idx in range(idx_begin, len(candidates)):             candi = candidates[idx]             if candi <= target - sm:                 self.rec(candidates, idx, target, pathes + [candi], sm + candi, output)             else: # early stop                 break

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul