[LEET CODE] 39. Combination Sum

# Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input. Constraints: 1 <= candidates.length <= 30 1 <= candidates[i] <= 200 All elements of candidates are distinct. 1 <= target <= 500

 

# My Answer

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result=[] # 리턴할 결과 리스트
        temp=[] # 하나씩 저장
        def dfs(nums,target):
            if target ==0: # target이 0이 되면 결과 리스트에 넣어준다
                result.append(temp[:])
                
            for i in range(len(nums)):
                if nums[i] > target: # 남은 target보다 큰 숫자일 경우 다음 숫자로 넘어감
                    continue
                temp.append(nums[i])
                dfs(nums[i:],target-nums[i]) # target에서 현재 숫자 빼준 후 재귀 호출
                temp.pop() # 다음 숫자 계산을 위해서 pop()
        dfs(candidates,target)
        return result

 

# Solution 1 - DFS로 중복 조합 그래프 탐색

class Solution:
    def combinationSum(self, candidates: List[int], target: int) \
            -> List[List[int]]:
        result = []

        def dfs(csum, index, path):
            # 종료 조건
            if csum < 0: # 합이 target보다 커진 경우 빠져나가기
                return
            if csum == 0: # 합이 target이 되면 결과 리스트에 추가
                result.append(path)
                return

            # 자신 부터 하위 원소 까지의 나열 재귀 호출
            for i in range(index, len(candidates)):
                dfs(csum - candidates[i], i, path + [candidates[i]])

        dfs(target, 0, [])
        return result

순열로 풀이하려면 (순서 상관 O)

dfs(csum - candidates[i], 0, path + [candidates[i]])

로 항상 처음부터 탐색