Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-09-09 12:07:25
https://leetcode.com/problems/combination-sum-iv/description/
377. Combination Sum IV
給你一個只包含不重複正整數的陣列 nums,和一個數字 target,求出只使用 nums 裡面
的數字共有幾種方式可以組成 target。
Example 1:
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Example 2:
Input: nums = [9], target = 3
Output: 0
思路:
1.NSum加上動態規劃,我們可以用 target - num 檢查是否可以加上當前數字得到和,
把所有的總和加總即可。
2.因為有很多重複計算所以用 memoization 來暫存已經算過的結果。
Java Code:
作者: JerryChungYC (JerryChung)   2023-09-09 12:39:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com