LeetCode 筆記 - 377. Combination Sum IV

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

完成 🥰

也許你也會想看看