LeetCode 筆記 - 39. Combination Sum

Posted on 標籤
解析如何從數列中找出相加等於目標值的所有不重複組合，且數字可無限重複使用。本文教學使用深度優先搜尋（DFS）配合排序優化，透過剪枝技術跳過無效的分支，達成在廣大搜尋空間中精確搜集目標組合的目的。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 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

也許你也會想看看