[LeetCode] 39. Combination Sum [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Combination Sum - LeetCode>

1. 문제 (조합의 합)

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라.

각 원소는 중복으로 나열 가능하다.

2. 풀이

• DFS를 이용한 풀이

3. 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        def dfs(csum, idx, path):
            if csum < 0:
                return
            if csum == 0:
                ret.append(path[:])
                return

            for i in range(idx, len(candidates)):
                dfs(csum - candidates[i], i, path + [candidates[i]])

        ret = []
        dfs(target, 0, [])
        return ret

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	80 ms	14.2 MB	python3

 

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋