LeetCode 40(Combination Sum II, Python)

1. 문제 링크

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

Combination Sum II - LeetCode

2. 문제 설명

• 기존 Combination Sum(Leetcode39)의 업그레이드 버전으로, constraint가 하나 더 추가된 문제
• 후보 숫자의 모음인 candidates라는 리스트, target 숫자가 주어졌을 때, candidates numbers의 합이 target이 되는 unique한 조합을 찾아서 반환하는 것
  • 여기서 이전 문제와의 차이는, candidates에 있는 elements들은 combination안에서는 딱 한번만 쓰여야 하는 것! 
• 예시1) candidates = [10,1,2,7,6,1,5] 이고, target=8 이라면, 
  • 합해서 8이 되는 조합인, [[1,1,6], [1,2,5], [1,7], [2,6]]이 정답이 된다.
  • 이전 문제에서는 무한하게 중복이 허용되었어서, [1,1,1,1,1,1,1,1] 또한 답으로 추가가 되었는데, 이번문제에서는 이것이 제한되어있음

3. 기존 풀이

• 이전 문제를 풀고 gpt한테 개선된 풀이를 물어봤는데, backtracker 알고리즘을 이용해야 잘 풀렸고,
• 해당 풀이에 조건을 더 추가하는 방식으로 코드를 짰다.
• 이전 문제에서는 backtracker가 break되는 조건이
  • candidates[i] > remain일 때였고, 이를 제외하고는, backtracker를 또 호출하는 구조의 재귀를 썼었다.
  • 이렇게 하면, 무한히 중복해서 호출할 수 있기 때문에,
    • candidates_dict이라는 딕셔너리를 두고, elements를 key, frequency를 value로 하는 사전을 만들어두었다.
    • 만약 현재까지의 path에서 element의 등장 횟수가, candidates_dict[element]보다 크거나 같다면, 이는 path에 추가하면 안되기 때문에 pass를 하고, 그 이외의 경우에만, backtracker를 호출하는 구조로 짰다
    • 이렇게만 하면, 중복이 제거가 되지 않는 이슈가 있었는데 ([1,1,6], [1,1,6]) 처럼 같은 게 두번 등장
      • 이걸, if path not in output: output.append(path)를 하게 되면, runtime이 너무 오래 걸렸고, 
      • 어차피 candidates_dict를 통해 path에 append되는 element의 수는 제한이 되기 때문에, 
        • backtracker함수를 쓰기 전에, candidates의 중복을 없애주었다. (list(set(candidates))
    • runtime 99.6%로 굉장히 높게 통과!

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        candidates_dict = {}
        for i in candidates:
            if i not in candidates_dict:
                candidates_dict[i] = 1
            else:
                candidates_dict[i] +=1
    
        def backtracker(remain, path, start):
            if remain ==0:
                output.append(path)
                return
            for i in range(start,len(candidates)):
                if candidates[i] > remain:
                    break
                if path.count(candidates[i]) >= candidates_dict[candidates[i]]:
                    pass
                else:
                    backtracker(remain-candidates[i], path+[candidates[i]], i) 
    
        output=[]
        candidates=list(set(candidates))
        candidates.sort()
        backtracker(target, [], 0)
        return output

 

4. 다른 풀이 

• 내가 푼 풀이에서는, dictionary로 저장해야 하는 것, candidates의 중복을 제거해서 backtracker를 호출해야 하는, 부가적인 게 코드에 추가가 되어야 하는데,
• 아래처럼 만약 "직전의 element가 이번과 동일하면" continue를 해서 다음 루프로 가게 추가하면서 기존에 제공된 개수 이상을 사용하며 조합을 만들지 못하도록 강제하여 조금 더 깔끔한 풀이.
  • 직관적으로 이해하는데는 약간 시간이 걸렸다.
  • 처음에 [1,1,2,4,5], target=6일 때, 그럼 [1,1,4]도 안만들어지는 것 아닌가 생각했는데,
    • backtrack([1], 5, 1)이 다시 backtrack을 돌 때는, next_curr = curr 상태에 1이 하나 더 나오기 때문에 추가가 가능하며, 그 이상의 추가일 때만 continue가 걸리는 것

class Solution:
    def combinationSum2(self, A: List[int], target: int) -> List[List[int]]:

        def backtrack(comb, remain, curr):
            if remain == 0:
                results.append(comb)
                return

            for next_curr in range(curr, len(A)):
                if next_curr > curr and A[next_curr] == A[next_curr - 1]:
                    continue

                pick = A[next_curr]
                if remain - pick < 0:
                    break

                backtrack(comb + [pick], remain - pick, next_curr + 1)
 

        A.sort()

        results = []
        backtrack([], target, 0)

        return results

 

5. 배운 점 

• backtrack에 익숙해지기
  • 언제 break를 걸 것인가?
  • 언제 recursive가 종료되는가.