leetcode.com 40. Combination Sum II

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

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

 

40번 이 문제를 풀어 보기전에, 꼭 39번 문제를 풀어 보시기를 추천 드립니다. 39번 문제가 어렵다면, 아래 문제 풀이와 소스를 참고하세요.

 

leetcode.com 39. Combination Sum

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

문제 풀이: https://codapul.blogspot.com/2024/04/leetcodecom-39-combination-sum.html

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

 

 40번 문제는 39번 문제의 연장선에서 좀더 난이도가 올라간 문제입니다. 기본적으로 문제 풀이 방법은 39번과 동일하지만, 두 문제가 다른 점이 하나 있습니다. 바로 아래 문장입니다.

39번 문제에는 중복된 숫자가 없고, 모두 다른 숫자만 candidates변수에 들어 있습니다.

Given an array of distinct integers candidates

 

하지만, 40번 문제에는 아래와 같이 기술되어 있습니다.

Given a collection of candidate numbers (candidates)

따로, 중복된 숫자가 없다는 문제 설명이 없으므로, candidates 리스트에는 중복된 숫자가 있다고 가정하고 문제를 풀이해야 합니다.

Example 1번을 보면, [10,1,2,7,6,1,5]으로 주어 지는 대요 1이 중복되어서 두 번 들어가 있습니다. 이 문제에서 구하는 답은 조합(combination)이기 때문에, 앞쪽에 1이 첫번째 숫자로 와도 뒤쪽에 있는 1이 첫번째 숫자로 와도, 모두 같은 조합입니다. 여기서 중복이 발생하게 됩니다.

 문제 39번에서는 중복을 방지 하기 위해서, candidates 를 처음부터 방문하지 않고, idx_begin 변수를 두어서, idx >= idx_begin 이 관계가 성립하도록, 재귀함수를 호출 했었습니다.

하지만, 40번 문제에서는 애초에 candidates에 중복된 숫자가 들어 있기 때문에 다른 접근 방식이 필요합니다. 이런 중복이 그렇게 큰 문제일까? 라고 생각하 실 수도 있지만, 아래와 같은 테스트 케이스에서는 매우 많은 중복이 발생하게 됩니다.

candidates리스트 안에 1이 30개 있음

target 값은 30

이렇게 되면, 1을 계속 중복해서 방문하면서도, 매번 같은 조합을 만들게 됩니다. 따라서, 이런 중복을 막을 방법이 필요한대요, 바로 지나온 길을 기억해 두는 것입니다.

 좀더 자세한 설명을 위해서 candidates [1, 1, 1], target 3인 경우를 알아보겠습니다.

첫번째 재귀함수, 첫번째 1을 선택합니다. 합은 1, visited에 [1]을 저장해 둡니다.

두번째 재귀함수, 두번째 1을 선택합니다. 합은 2, visited에 [1,1]을 저장해 둡니다.

세번째 재귀함수, 세번째 1을 선택합니다. 합은 3, visited에 [1,1,1]을 저장해 둡니다.

Target 3이 되는 조합 [1,1,1]을 찾았으니, output리스트에 저장하고, 리턴 합니다.

다시 두번째 재귀함수, 세번째 1을 선택합니다. 합은 2, visited에 보면 [1,1]이 저장되어 있습니다.

따라서, 세번째 재귀함수를 호출하지 않고, 리턴 합니다.

다시 첫번째 재귀함수, 두번째 1을 선택합니다. 합은 1, visited에 [1]이 저장되어 있습니다.

재귀함수를 호출하지 않습니다.

 

문제를 조금 더 빨리 풀이하는 방법을 알아보겠습니다.

Example 1은 target 값이 8 입니다. candidates를 sort를 하면, 한번 아래 if 문을 통과하지 못하면, break로 for 루프를 빠르게 종료할 수 있습니다.

여기서 sm 은 pathes에 있는 모든 원소를 합한 값이고,

candidates리스트에 있는 원소 중에 선택된 원소 1개가 candi 입니다.

for idx in range(idx_begin, len(candidates)):     candi = candidates[idx]     if sm + candi <= target:         … … …     else:         break

 

한번 if 에서 실패 하면, 해당 candi 뒤에 있는 숫자들은 모두 candi 와 같거나 큰 숫자이기 때문에, break를 사용해서 for 루프를 빠저 나올 수 있습니다.

이렇게 모든 루프를 다 돌아서, 모든 candi를 방문하지 않고, 빨리 for 루프를 종료하는 방법을 early stop이라고 합니다.

 

39번 문제 풀이와는 다르게, 40번 문제에서는 visited가 필요합니다. 기본값으로 False를 가지도록 딕셔너리 변수를 만들어 보겠습니다.

visitied: dict = defaultdict(lambda: False)

 

Lambda를 사용해서 기본값으로 False를 가지는 딕셔너리 변수를 만들었습니다.

이 딕셔너리의 키는 pathes리스트를 tuple로 변환해서, 딕셔녀러의 키로 사용합니다.

따라서 아래와 같이 [1,1] 같은 리스트를 튜플(1,1)로 변환해서, 딕셔너리의 키로 사용하는 것입니다. 딕셔너리는 기본값으로 False를 가지고 있기 때문에 아래와 같이 if else를 구현할 수 있습니다.

if visitied[tuple(pathes + [candi])]:     continue else:     visitied[tuple(pathes + [candi])] = True

 

첫 방문이면 False라서, else: 구문이 실행되고, True로 변경합니다. 따라서, 한번 [1,1]로 방문한 뒤에는, 중복된 1이 있다고 해도, [1,1]을 방문하지 않게 됩니다.

문제를 푸는 전체 코드는 아래와 같습니다.

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

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

from collections import defaultdict from typing import List class Solution:     def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:         output: List = []         visitied: dict = defaultdict(lambda: False)         candidates.sort()         self.rec(candidates, 0, target, [], 0, output, visitied)         return output     def rec(self, candidates: List, idx_begin: int, target, pathes: List, sm: int, output: List, visitied: dict):         if target == sm:             output.append(pathes)             return         for idx in range(idx_begin, len(candidates)):             candi = candidates[idx]             if sm + candi <= target:                 if visitied[tuple(pathes + [candi])]:                     continue                 else:                     visitied[tuple(pathes + [candi])] = True                 self.rec(candidates, idx + 1, target, pathes + [candi], sm + candi, output, visitied)             else:                 break