LeetCode 筆記 - 377. Combination Sum IV

Posted on

題目在此 377. Combination Sum IV

給定數列與目標數，請給出數列中有幾種相加等於目標數的排列組合

解題思維

終於解到第四題了

如果沒解過一、二、三題，你可以看看
LeetCode 筆記 - 39. Combination Sum
LeetCode 筆記 - 40. Combination Sum II
LeetCode 筆記 - 216. Combination Sum III

這題一樣是用 Depth First Search 跑一次就可以了
你以為我要這麼說？太天真了

這題要用 Dynamic programming 🥰

整體概念是，從 1 開始跑到目標數
如果 candidate 等於目標數，表示多一種可能，因為有新的 candidate 加入
不然就持續加總加入 candidate 之前的可能性

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum4(self, candidates: List[int], target: int) -> int:
        
        candidates = [n for n in candidates if n <= target]
        candidates.sort()
        
        dp = collections.defaultdict(int)
        
        for i in range(1, target + 1):
            for c in candidates:
                if c > i:
                    break
                    
                if c == i:
                    dp[i] += 1
                else:
                    dp[i] += dp[i - c]
        
        return dp[target]

完成 🥰

也許你也會想看看