Leetcode 39

Posted on | | 阅读数
Words count in article: 95 | Reading time ≈ 1

Question

Solution

Dfs来解。

先对candidates排序，然后对于candidates里面的每一个index遍历从其本身之后的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        candidates.sort()
        self.dfs(0, candidates, target, [], results)
        return results
    
    
    def dfs(self, index, candidates, target, temp, results):
        if target < 0:
            return 
        if target == 0:
            results.append(temp)
        for i in range(index, len(candidates)):
            self.dfs(i, candidates, target - candidates[i], temp + [candidates[i]], results)