377. Combination Sum IV
Question
Given an array of distinct integers
nums
and a target integertarget
, return the number of possible combinations that add up totarget
.The test cases are generated so that the answer can fit in a 32-bit integer.
Solution
记忆化搜索,memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。
递归DFS,记忆化剪枝,如果memo[]数组不为空,则直接返回记忆内容。
当total等于target时,该组合成立,返回1。
遍历nums[]数组中的每个元素,并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。
*非常奇怪的是,当我使用int[]数组进行记忆化搜索时部分case会超时,推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。
Code
1 | class Solution { |
377. Combination Sum IV
https://xuanhe95.github.io/2022/08/05/377-Combination-Sum-IV/