39. Combination Sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ret = []
        arr = [0]
        self.helper(ret, arr, candidates, target)
        return ret
        
    def helper(self, ret, arr, candidates, target):
        _sum = sum(arr)
        if _sum > target:
            return
        if _sum == target:
            ret.append(arr[1:])
            return
        for candidate in candidates:
            last_input = arr[-1]
            if candidate >= last_input:
                next_arr = arr.copy()
                next_arr.append(candidate)
                self.helper(ret, next_arr, candidates, target)

 

좀 더 좋은 solution...

본질적으로는 dfs 라는 점을 파악하면 더 쉽게 접근 가능,,,

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ret = []
        self.dfs(candidates, target, [], ret)
        return ret
        
    def dfs(self, nums, target, path, ret):
        if target < 0:
            return
        if target == 0:
            ret.append(path)
            return
        
        for i in range(len(nums)):
            self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)