Leetcode Python - 39. Combination Sum

Leetcode #39 - Combination Sum

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 39 ‘Combination Sum’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 dfs를 이용해 recursion하게 풀 수 있습니다.

전체 코드는 아래와 같습니다.

class Solution:
    def combinationSum(self, candidates, target):
        res = []
        self.dfs(candidates, target, [], res)
        return res
    
    def dfs(self, candidates, target, r, res):
        if target == 0:
            res.append(r)
            return
        if target < 0:
            return
        
        for i in range(len(candidates)):
            self.dfs(candidates[i:], target-candidates[i], r+[candidates[i]], res)

candidates 의 크기가 n target 이 m 일때

시간복잡도는

• 최악의 경우 O(n^m) (candidates에 1이 있을 경우 n번씩 for loop 계속 1씩 target이 줄어들면서 진행됨)

공간복잡도는

• 최악의 경우 O(m^2) : [1,1,1,…1] 처럼 m개 만큼 필요하고 다음은 m-1 … 될것이라 가정함