題目

LeetCode - 377. Combination Sum IV

解題思路

給定一相異整數之陣列以及一個目標整數 target，回傳可能的組合之數量其組合中的數字總和為 target。

可以看到每種數字可使用任意次。
觀察範例輸入一，nums = [1,2,3]、target = 4，其方法數分為以下三種：

  1. 1 + (target = 3 之方法)
  2. 2 + (target = 2 之方法)
  3. 3 + (target = 1 之方法)

可以看到這其實就是一個dp的問題，dp[i]表示為target為i，從nums能產生出多少組解，有一個關鍵為dp[0]會為1，因為當target為0時，會有1組解為空。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum4(self, N: List[int], T: int) -> int:
        # dp[i]表示為target為i，從N中產生出多少組解
        dp = [0] * (T + 1)
        dp[0]=1 #表示target為0時，有一組解就是啥都不放
        # 以N=[1,2,3] , T=7
        # dp[1] = {0} + 1
        # dp[2] = {2-1} + 1
        #       = {2-2} + 2
        #       .
        #       .
        #       .
        for i in range(1,T+1):
            for j in range(len(N)):
                if i-N[j]>=0:
                    dp[i]+=dp[i-N[j]]
        return dp[T]