Leetcode 40. 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.

사용가능한 숫자들의 배열이 주어지고, 이들을 더해 완성할 타겟 값이 주어진다.
배열에 들어간 숫자들을 이용해 타겟 합을 가지는 부분배열을 만들때,
모든 부분배열의 조합을 중복없이 전부 리턴하시오.

예시

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

제한

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

풀이법

• 백트래킹을 사용한다.
• 단, 한번의 백트래킹을 시도할때 미리 타겟값을 넘는 경우는 제외해야 하며
• 백트래킹 함수 내에서 다음 값을 고를때엔 같은값을 두번 선택하지 않도록 해야 한다.
  • 이를 위해 candidates 를 미리 오름차순으로 정렬해 두었다.

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

        candidates.sort()

        def finder(last_index, left_value):

            if left_value == 0:
                ans.add(tuple(app))
                return

            prev = None
            for index in range(last_index + 1, len(candidates)):
                if left_value - candidates[index] < 0:
                    return
                if prev != candidates[index]:
                    prev = candidates[index]
                    app.append(candidates[index])
                    finder(index, left_value - candidates[index])
                    app.pop()

        finder(-1, target)

        return ans

여담

이게 왜 빠름?