主題

LeetCode - 377. Combination Sum IV 解題心得

Not In My Back Yard | 2021-05-01 00:00:05 | 巴幣 0 | 人氣 34

題目連結:


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

答案保證可以存進一個 32 位元整數裡。

限制:
1 ≦ nums.length ≦ 200
1 ≦ nums[i] ≦ 1000
nums 中所有元素相異。
1 ≦ target ≦ 1000
 
進階: 如果給定的陣列中允許有負數呢?會如何影響這道問題?我們需要為題目加上什麼限制才能使得題目允許負數之存在?



範例測資:
範例 1:
輸入: nums = [1,2,3], target = 4
輸出: 7
解釋:
可能的組合方式為:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
注意到不同順序的數列視為不同組合。

範例 2:
輸入: nums = [9], target = 3
輸出: 0


解題思維:
可以看到每種數字可使用任意次。

觀察範例輸入一,nums = [1,2,3]、target = 4,其方法數分為以下三種:
1 開頭 + (target = 3 之方法)、
2 開頭 + (target = 2 之方法)、
3 開頭 + (target = 1 之方法)、
可以看到這其實跟走樓梯問題(如這題)相當類似。只是現在可以走的步伐存在了 nums 陣列裡。

因此,我們可以仿照一般的走樓梯問題去計算 target 的方法數(等同於在有 nums.length 種步伐時,走到第 target 階有多少種走法)。

不過要注意的是,因為題目提及的是答案可以存入 32 位元整數,而非 32 位元「有號」整數。所以對於 C/C++ 來說需要使用 32 位元無號整數來存答案才會得到正確值。



那麼,如果 nums 裡有負數呢?此時代表著我們可以走回頭路(一直在樓梯上上下下)使得方法數有機會變為無限大。因此,要使得答案為有限值有幾種限制方式:
一:不要有負數(廢話);
二:限制方法的「長度」上限;
三:每種負數有使用次數之限制;
四:所有數字不管正負都有使用次數限制;




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作