Combination Sum LeetCode solution in Python

1
# Runtime: 95 ms (Top 82.54%) | Memory: 14.1 MB (Top 72.96%)
2
class Solution:
3
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
4

5
        path = []
6
        answer = []
7

8
        def dp(idx, total):
9
            if total == target:
10
                answer.append(path[:])
11
                return
12
            if total > target:
13
                return
14

15
            for i in range(idx, len(candidates)):
16
                path.append(candidates[i])
17
                dp(i, total + candidates[i])
18
                path.pop()
19

20
        dp(0, 0)
21
        return answer