Page tree
Skip to end of metadata
Go to start of metadata

Too slow... (5%, 76%) → 소트 (11%, 51%) → 제약 조건 (45%, 76%)

Combination Sum II
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if sum(candidates) < target:
            return []

		# 소트
        candidates.sort()

        result = []
        def dfs(nums, path):
            if sum(path) > target:
                return True
            elif sum(path) == target:
                path.sort()
                if path not in result:
                    result.append(path)
                return True

            if len(nums) == 0:
                return False

			# 제약 조건
            if not dfs(nums[1:], path + [nums[0]]):
                dfs(nums[1:], path)        

        dfs(candidates, [])
        
        return result
  • No labels