[LeetCode - Didi Labs 기출문제] 40. Combination Sum II

40. Combination Sum II

 

Medium

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

---

문제 풀이

숫자 배열이 주어 졌을때 각 숫자들을 선택하여 더한 값이 target 과 같은 경우 숫자들을 찾는 문제이다.

만약 조합을 무조건적으로 모두 검색한다면 n! 시간복잡도가 걸려서 문제를 풀 수없다.

그래서, 정렬을 사용하거나 counter 를 사용해야 문제가 풀린다.

정렬

• candidates배열을 정렬한다.
• 기존의 조합 백트래킹과 마찬가지로, 숫자를 더하고 임시배열에 숫자들을 추가하면서 백트레킹을 진행한다.
• 만약 합친 숫자가 target 과 같으면 정답으로 넣어준다. 
• 여기서, 중복된 리스트를 거르기위해 사용하는 방법은 정렬과 인덱스이다.
• 숫자 배열을 정렬을 하면 같은 숫자들은 일렬로 나란해진다. 
• 첫번째 숫자 선택후, 두번째, 세번째... 등의 숫자 선택의 순번에서는 중복된 숫자 선택을 처리하지 않는다. 
• 하지만 백트래킹에서 몇 번째 숫자를 선택할 당시, 같은 숫자를 선택하지 못하게 막는다.
• 즉, 다음 레벨의 브랜치에서는 중복된 숫자를 선택할 수 있지만 같은 레벨의 브랜치에서는 중복된 숫자 선택을 막는것이다. 
• 이렇게 하면, 재귀함수에서 새로운 숫자를 선택할때 딱 한번의 숫자를 선택하게된다, 이와 반대로 같은 레벨에서의 다중 선택시 정렬된 배열에서 이전 자리의 숫자와 같다면 선택을 띄워 넘겨 주자.
• 이미 정렬된 배열로 어떻게 중복을 제거하는지 보자, 예를 들어 1, 1, 3, 2, 1, 1, 2 이렇게 되있고 target 이 3이라면 1, 1, 1, 1, 2, 2, 3 이런식으로 정렬될 것이다.
• 숫자를 순서대로 선택한다면, 
• 첫째: 1
• 둘째: 1
• 셋째: 1
• 위 처럼 세번째 까지의 숫자가 선택되어 (1, 1, 1) 이 되었다면 더 이상 (1, 1, 1)을 선택하면 안된다. 
• 다시 두번째에서 셋째 숫자를 선택하려 했을때, 이미 (1, 1)이 완성되어 있는 상태이다.
• 이 상태에서는 세번째 숫자를 선택해야하는 상황인데 이때 정렬되어 있는 배열에서 index 3 위치 숫자와 2위치의 숫자가 같다면 선택을 피해주는 것이다.
• 이렇게하면, 새로운 자리의 중복되는 숫자의 선택은 가능하지만 기존 자리의 중복된 숫자 선택을 불가능하게 된다. 

counter

• 숫자의 갯수를 새는 Counter 함수를 사용하여 배열을 만든다.
• 그 배열의 값들을 (숫자 값, 숫자의 갯수)로 변환해준다. 
• 그리고 백트레킹으로 숫자들을 선택할때 이 카운터 배열을 사용하여 숫자를 선택해준다.
• 배열에서 숫자들을 선택하는게 아니라 카운터 배열에서 숫자의 갯수로 숫자를 선택하는 옵션에 관여한다면,
• 숫자 선택 배열의 중복을 막을 수 있다. 
• 몇번째 위치의 숫자를 선택하는 방법이아니라, 숫자 a 가 몇개 존재하는데
• a 를 선택할때마다 숫자의 갯수로 차감하고 더 해준다, 또한 숫자 갯수를 모두 선택했다면 다른 숫자 선택으로 넘어간다. 
• 숫자 선택의 기준의 a 숫자의 갯수로 판별될 수 있는 것이다. 
• 재귀함수의 다음 레벨에서 숫자를 선택할때 선택할 수 있는 숫자의 갯수가 가변적으로 계속 바뀌는 형식이다.
• 즉 쉽게말해, 숫자를 어떻게 몇개 고를것인가가 아니라 각각의 숫자를 몇개 뽑을 것이냐라는 관점으로 바뀌게된다. 
• 나머지 숫자를 선택하는 방식은, 기존의 조합 백트레킹과 같다.

소스 코드

 정렬 + 인덱스 

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        self.ans = []
        def bt(idx, total, temp, candidates, target):
            if total > target: return
            if total == target:
                self.ans.append(temp.copy())
                return
            
            for i in range(idx, len(candidates)):
                if i > idx and candidates[i] == candidates[i - 1]: continue
                if candidates[i] > target: break
                temp.append(candidates[i])
                bt(i + 1, total + candidates[i], temp, candidates, target)
                temp.pop()
        bt(0, 0, [], candidates, target)
        return self.ans

 

Counter

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        
        def bt(temp, remain, curr, cnt):
            if remain == 0:
                self.res.append(list(temp))
                return
            elif remain < 0:
                return
            
            for nxt in range(curr, len(cnt)):
                can, freq = cnt[nxt]
                if freq <= 0:
                    continue
                    
                temp.append(can)
                cnt[nxt] = (can, freq - 1)
                bt(temp, remain - can, nxt, cnt)
                cnt[nxt] = (can, freq)
                temp.pop()
        
        cnt = Counter(candidates)
        cnt = [(c, cnt[c]) for c in cnt]
        bt([], target, 0, cnt)
        
        return self.res