[leetcode] combination sum

combination sum

• 숫자 집합(candidates)과, target 숫자가 주어진다
• 숫자 집합의 숫자를 조합해서 target이 되는 모든 경우를 나열
• 숫자 집합의 원소를 여러번 사용할수 있다

solution

• dfs를 통해서 작은 원소부터 cur에 하나씩 추가
• target에 도달하면 결과값에 포함
• target을 초과하는 경우에는 탐색 종료
• 한 원소를 추가하면 다음 재귀 에서는 그 원소보다 작은 원소는 추가할수 없게 한다

code

class Solution(object):
    def combinationSum(self, candidates, target):

        candidates = sorted(filter(lambda x : x <= target,candidates))
        results = []
        def dfs(cur=[],elements=candidates):
            if sum(cur)==target:
                results.append(cur[:])
                return

            for i,el in enumerate(elements):
                # 가지 치기
                if sum(cur) + el > target : break
                cur.append(el)
                dfs(cur,elements[i:])
                cur.pop()
        dfs()
        return results