Page tree

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Code Block
languagepy
themeEmacs
titleCombination Sum II
linenumberstrue
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[1:], [candidates[0]])
        dfs(candidates[1:],
[])         
        return result