[leetcode] Combination Sum 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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

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

나의 코드

class Solution(object):
    def __init__(self):
        self.answer = []

    def combinationSum2(self, candidates, target):
    	# 숫자가 이전 숫자와 동일할 경우 가지치기 할 수 있도록 정렬
        candidates.sort()

        def dfs(selected, x):
            if sum(selected) == target:
                self.answer.append(selected)
                return
			
            # target보다 합계가 커지면 탐색을 중단
            if sum(selected) > target:
                return
            
            for i in range(x, len(candidates)):
            	# ⭐️ level이 같은 경우 중복 조합 방지 (아래에 그림과 함께 설명)
                if i > x and candidates[i] == candidates[i - 1]:
                    continue
                dfs(selected + [candidates[i]], i + 1)
        
        dfs([], 0)
        return self.answer

위의 빨간색 노드는 가지치기(x)를 이용하여 방문하지 않는 노드이다.
다음 level에서는 현재까지의 노드의 다음 노드부터 방문하게 하려면, 재귀 호출 시 for문의 start로 i + 1을 인자로 전달하면 된다. 이 방법은 이제 문제들을 풀어보면서 익숙해졌는데, 이 문제에서처럼 candidates 자체에서 동일한 숫자가 여러번 나오도록 제시될 때 중복을 제거하는 건 도통 풀이가 생각이 안났다.

for문 내에서 조건을 줘야 한다.

1) 같은 레벨일 경우 중에서도 (i >= x)
2) 이미 이전에 방문을 한 노드 중에 (방문 가능한 첫번째 노드(x) 제외하고 i > x로 좁혀짐)
3) 숫자까지 동일한 노드가 있다면

탐색을 중단하고 continue하면 된다.

처음에는 i > x라고 생각을 못하고 이전 숫자랑 동일한 경우를 제외할 생각만 했었는데, level이 다르면 같은 조합 내에서 숫자가 중복되어서 나와도 상관이 없으므로 위와 같은 조건을 줘야 하는 것이다.