40. Combination Sum II

문제 링크 : https://leetcode.com/problems/combination-sum-ii/

순서대로 정렬되지 않은 candidates가 있을 떄,
각 합이 target이 될 수 있도록 묶는 문제이다.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        def dfs(group, idx) :
            if sum(group) > target : 
                return
            if sum(group) == target :
                ans.append(group)
                return
            for i in range(idx, len(candidates)):
                if i > idx and candidates[i] == candidates[i-1]:
                    continue
                dfs(group + [candidates[i]], i +1)
        dfs([], 0)
        return ans

주어진 리스트의 요소를 통해 target을 만들어야합니다.
만들 수 있는 경우의 수를 리스트에 넣어 반환한다.

if i > idx and candidates[i] == candidates[i-1]:
continue
를 넣은 이유: 중복방지

DFS를 이용하면 풀 수 있습니다.

Runtime: 78 ms, faster than 83.25% of Python3 online submissions for Combination Sum.
Memory Usage: 14 MB, less than 60.53% of Python3 online submissions for Combination Sum.

다시 한번 꼭 풀어봐야지