40. Combination Sum II

[zeikar]

Problem link

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

Problem Summary

배열과 수가 주어질 때 합이 수가 되도록 만드는 배열의 조합을 모두 구하는 문제.

Solution

n=100이라 힘들것 같지만 완전탐색으로 풀린다.
일단 target의 범위도 작고, 중복을 제외하는 등 가지치기가 꽤 된다. 반대로 말하면 가지치기를 못하면 시간초과가 난다.

중복을 제거하기 위해 일단 정렬. 한 탐색 내에서 같은 원소는 건너뛰는 방식으로 돌려야 한다.

예를 들어 [1,1,1] 이고 2를 만들어야 할 때, [1,1]이 한번만 나와야 하는데 이는 탐색할 때 같은 원소는 한번만 탐색하게 해야 한다.
말로는 좀 어려운데 코드를 보면 이해가 되긴 한다.

if i > idx and candidates[i] == candidates[i - 1]:

위 if문인데 한번 for 문 탐색할 때 같은 원소는 한번만 돌도록 가지치기를 해야 한다. [1,1]처럼 같은 원소는 다른 for문에서 뽑아내야 한다.

Source Code

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        candidates.sort()
        ans = []

        def solve(idx, num, l):
            if num < 0:
                return
            if num == 0:
                ans.append(l)
            if idx == n:
                return

            for i in range(idx, n):
                if i > idx and candidates[i] == candidates[i - 1]:
                    continue
                solve(i + 1, num - candidates[i], l + [candidates[i]])

        solve(0, target, [])
        return ans