【Leetcode】377. 组合总和 Ⅳ-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Leetcode】377. 组合总和 Ⅳ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

题目链接🔗
给你一个由不同整数组成的数组 $n u m s$ ，和一个目标整数 $t a r g e t$ 。请你从 $n u m s$ 中找出并返回总和为 $t a r g e t$ 的元素组合的个数。

题目数据保证答案符合 $32$ 位整数范围。

示例 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

提示：

$\leq nums.length \leq 200$

$\leq nums[i] \leq 1000$

$n u m s$ 中的所有元素 互不相同

$\leq target \leq 1000$

思路

这道题可以使用动态规划来解决。我们定义一个数组 $d p$ ，其中 $d p [i]$ 表示选取的元素之和等于 $i$ 的方案数。目标是求 $d p [t a r g e t]$ 。

动态规划的边界是 $d p [0] = 1$ ，因为只有当不选取任何元素时，元素之和才为 $0$ ，所以只有 $1$ 种方案。

对于 $\leq i \leq target$ ，我们遍历数组 $n u m s$ 中的每个元素 $n u m$ ，当 $\leq i$ 时，将 $d p [i - n u m]$ 的值加到 $d p [i]$ 。

最终， $d p [t a r g e t]$ 的值即为答案。

通过遍历数组 $n u m s$ 中的每个元素来更新 $d p [i]$ 的值，不同的选取顺序都会被考虑到。

代码

class Solution {
public:
    long long dp[1010];
    int combinationSum4(vector<int>& nums, int target) {
        dp[0]=1;
        for(int i=0;i<=target;i++){
            for(int j=0;j<nums.size();j++){
                if(i>=nums[j])
                dp[i]=(int)dp[i]+dp[i-nums[j]];
            }
        }
        return dp[target];
    }
};