leetCode - Combination Sum

leetcode.com/problems/combination-sum

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        def DFS(node, combination, summation):
            combination.append(node)
            summation += node
            if summation == target:
                combinations.append(combination[:])
                summation -= combination.pop()
                return
            for child in [child for child in deq_candidates if child >= node and child + summation <= target]:
                DFS(child, combination, summation)
            summation -= combination.pop()
            
        combinations = []
        
        candidates.sort()
        n_candidates = len(candidates)
        deq_candidates = collections.deque(candidates)
    
        for i in range(n_candidates):
            combination = []
            DFS(candidates[i], combination, 0)
            deq_candidates.popleft()
            
        return combinations

 

순열이 아닌 조합을 찾을 때는

1. 오름차순으로 정리

2. 자식 노드들을 부모 노드 이상의 노드들로 구성

하면 된다.