LeetCode 筆記 - 39. Combination Sum

Posted on

題目在此 39. Combination Sum

給一個數列與目標數，請從數列找出相加的組合等於目標數，數字可以重複使用

解題思維

這題就是用 Depth First Search 跑一次就可以了

有個小技巧是可以先 Sorting，來跳過一些計算

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        candidates.sort()
        
        self.result = []
        def dfs(last_index, result, count):
            if count == target:
                self.result.append(result)
                return
            
            for i, candidate in enumerate(candidates):
                if i < last_index:
                    continue
                if count + candidate > target:
                    break
                
                dfs(i, result + [candidate], count + candidate)
        
        dfs(-1, [], 0)
        
        return self.result

也許你也會想看看