※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1694232448.A.A23.html
Re: [閒聊] 每日LeetCode
| 看板 | Marginalman |
|---|---|
| 作者 | Rushia (みけねこ的鼻屎) |
| 時間 | 2023-09-09 12:07:25 |
| 留言 | 0則留言 (0推 0噓 0→) |
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：
--------------------------------------------------------
class Solution {
private Integer[] memo;
public int combinationSum4(int[] nums, int target) {
memo = new Integer[target + 1];
return dfs(nums, target);
}
private int dfs(int[] nums, int target) {
if (target == 0) {
return 1;
}
if (target < 0) {
return 0;
}
if (memo[target] != null) {
return memo[target];
}
int ans = 0;
for (int num : nums) {
ans += dfs(nums, target - num);
}
return memo[target] = ans;
}
}
--------------------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1694232448.A.A23.html
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1694232448.A.A23.html