[LeetCode 해석 및 풀이] 40. Combination Sum II(조합합 II)

LeetCode 문제 해석 및 풀이 방법

문제 40. Combination Sum II(조합합 II)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

 

Each number in candidates may only be used once in the combination.

 

Note: The solution set must not contain duplicate combinations.

 

한글

후보 번호(candidates) 및 목표 번호(target)의 모음이 주어지면 후보 번호의 합이 target인 candidates 에서 모든 고유한 조합을 찾습니다.

 

candidates 의 각 번호는 조합에 한 번만 사용할 수 있습니다.

 

참고: 답에 중복된 조합이 포함되어서는 안 됩니다.

 

제한조건

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

 

입출력 예

입력	출력
candidates = [10,1,2,7,6,1,5], target = 8	[[1,1,6],[1,2,5],[1,7],[2,6]]
candidates = [2,5,2,1,2], target = 5	[[1,2,2],[5]]

 

해답 및 해설

파이썬 (Python)

백트레킹 알고리즘을 이용한 풀이

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        num_count = {}
        for num in candidates:
            num_count[num] = num_count.get(num, 0) + 1

        num_order = [*num_count.keys()]
        num_order.sort()

        answer = []

        def helper(target, depth, num_temp):
            if target == 0:
                answer.append(num_temp)
                return

            for i in range(depth, len(num_order)):
                check_num = num_order[i]
                if target < check_num:
                    return

                count = num_count[check_num]
                new_num_temp = num_temp.copy()
                new_target = target - check_num

                while count > 0 and new_target >= 0:
                    new_num_temp += [check_num]
                    helper(new_target, i+1, new_num_temp)
                    count -= 1
                    new_target -= check_num
        
        helper(target, 0, [])
 
        return answer

 

neetcode 로드맵에 나온대로 백트레킹을 이용한 풀이. 39. Combination Sum일 때의 풀이를 살짝 변형하였다. 리스트의 원소들이 나오는 갯수를 세어준 다음 그것을 바탕으로 다음 작업을 하여 답의 중복을 없주었다.

 

while count > 0 and new_target >= 0:
    helper(new_target, i+1, new_num_temp)
    count -= 1
    new_target -= check_num
    new_num_temp += [check_num]

특이한 점은 다음처럼 반복문 시작이 아니라 끝에 원소를 더하도록 하면 답에서 마지막으로 추가되는 원소가 두 번 반복되는 오류가 있었다. 리스트 주소나 실행순서 관련된 문제인거 같은데 자세히는 알 수 없었다. 맨 처음 코드처럼 원소추가는 반복문 시작에 두니까 해당 문제는 사라졌다.

 

동적계획법을 이용한 풀이

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        num_count = {}
        for num in candidates:
            num_count[num] = num_count.get(num, 0) + 1

        dp = [[] for _ in range(target + 1)]

        for n, count in num_count.items():
            if n > target:
                continue
            
            for i in range(target, n, -1):
                j = 1
                last_target = i - n

                while j <= count and last_target > 0:
                    dp[i] += [comb + [n]*j for comb in dp[last_target]]
                    j += 1
                    last_target -= n
            
            k = 1
            while k <= count and k*n <= target:
                dp[k*n].append([n]*k)
                k += 1
                
        return dp[target]

 39. Combination Sum 문제와 다르게 중복되는 값은 피해야 하므로, 이전 저장된 값에서 새로운 숫자를 더해주는 작업은 반복문의 방향을 반대로 돌려주고, 새로운 숫자로만 이루어진 조합 추가도 나중에 해준다.