Leetcode 40. Combination Sum II - Python

Leetcode 40 문제 보기

 

문제 이해하기

1에서 50까지의 수로 이루어진 리스트 candidates가 있다. (1 <= candidates.length <= 100)

candidates의 원소 조합들 중 합이 target이 되는 경우의 조합들을 찾아라.

이 때, 각 원소들은 한 번씩 사용가능하며 중복되는 조합은 정답에서 제외되어야 한다.

 

아이디어 구상

단순히 조합을 구한다면 그리 어렵지 않은 문제다.

그러나 중복되는 조합을 제외해야하므로 약간의 트릭이 필요하다.

 

우선 target보다 큰 원소들은 필요가 없으니 제외시키고, 이후 Decision Tree를 그리며 생각해보자.

 

하나의 원소를 포함시키는 경우와, 그 원소와 같은 값의 원소들은 전부 제외시키는 경우,

위 2가지 경우로 가지를 뻗어나가자.

그렇게 되면 중복되는 조합이 생성되는 것을 미연에 방지하며 결과 리스트에 담을 수 있을 것이다.

이를 위해서는 우선 candidates가 정렬이 되어야 쉽게 풀이가 가능하다.

 

candidates = [10,1,2,7,6,1,5], target = 8인 test case를 살펴보자.

우선 candidates는 정렬이 되고 난 후, target인 8보다 큰 원소들은 제외시킨다.

By Mesotes

이후 위 논리에 의한 Decision Tree의 일부는 다음과 같다.

By Mesotes

이 때의 시간복잡도는 어떻게 될까?

n = len(candidates)라 할 경우, 기본적으로 Time Complexity ~ O(2 ^ n)일 것이다.

그러나 target보다 큰 원소를 제외하게 되면 n의 값은 감소할 것이고,

동일 원소를 스킵하는 등의 가지치기를 진행하기 때문에 실제 시간복잡도는 이보다 나을 것으로 생각된다.

 

풀이

정답을 담을 리스트를 선언하고 candidates를 정렬한다.

res = []
candidates.sort()

 

이후 DFS 탐색 시 target보다 큰 원소를 애초에 제외하고 탐색하기 위해 target보다 큰 원소의 index를 구한다.

last_idx = len(candidates)
    if max(candidates) > target:
        for c in range(len(candidates)):
            if candidates[c] > target:
                last_idx = c
                break

 

dfs()의 base case는 다음과 같다.

target에서 값을 계속 빼나갈 때, 값이 0이 되는 순간 해당하는 조합을 res에 담고 return한다.

if remain == 0:
    res.append(combi[:])
    return

 

dfs()의 재귀 부분은 다음과 같다.

아이디어 구상에서 살펴봤듯이, 탐색을 진행했던 원소와 동일한 값의 원소가 있을 경우, 그 원소의 탐색은 skip한다.

이 때, 이전 원소의 값을 보관하기 위한 변수 pre를 -1로 초기화한다. (candidates의 모든 원소는 1이상이기 때문)

탐색 시 remain < 0이 될 경우, 즉, target보다 조합의 합이 더 커질 경우 가지치기를 한다.

prev = -1
for i in range(idx, last_idx):
    if candidates[i] == prev:
        continue
    elif remain - candidates[i] < 0:
        break
    combi.append(candidates[i])
    dfs(combi, i + 1, remain - candidates[i])
    combi.pop()
                
    prev = candidates[i]

 

전체 코드는 다음과 같다.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        
        # exclude elements in candidates which are greater than target
        last_idx = len(candidates)
        if max(candidates) > target:
            for c in range(len(candidates)):
                if candidates[c] > target:
                    last_idx = c
                    break
        
        
        def dfs(combi, idx, remain):
            # base case
            if remain == 0:
                res.append(combi[:])
                return
            
            prev = -1 # 1 <= candidates[i] <= 50
            for i in range(idx, last_idx):
                if candidates[i] == prev:
                    continue
                elif remain - candidates[i] < 0:
                    break
                combi.append(candidates[i])
                dfs(combi, i + 1, remain - candidates[i])
                combi.pop()
                
                prev = candidates[i]
        
        dfs([], 0, target)
        return res

 

---

Leetcode 40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다