Leetcode Python - 40. Combination Sum II

Leetcode #40 - Combination Sum II

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

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

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

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

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

candidates 의 크기가 n target 이 m 일때

시간복잡도는

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

공간복잡도는

• 최악의 경우 O(n^2) : n+(n-1)+(n-2)+(n-3)…+1 = n(n+1)/2