leetcode之组合总和Ⅳ（C++）_lcr 104. 组合总和 ⅳ

作者：Gausst松鼠会 | 2024-03-30 02:51:06

踩

lcr 104. 组合总和 ⅳ

参考链接

https://leetcode-cn.com/problems/combination-sum-iv/

题目描述

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。
在这里插入图片描述

解题思路

动态规划问题。选择是数组中的元素，状态是target。状态转移方程为 $d p (n u m s, t a r g e t) = d p (n u m s, t a r g e t - n u m s [i])$

代码

class Solution {
public:
    unordered_map<int, int> mp;
    int combinationSum4(vector<int>& nums, int target) {
        if (target == 0)
        {
            return 1;
        }
        else if (target < 0)
        {
            return 0;
        }
        if (mp.count(target) == 1)
        {
            return mp[target];
        }
        int do_it = 0;
        int res = 0;
        for (int i = 0; i < nums.size(); i ++)
        {
            do_it = combinationSum4(nums, target-nums[i]);
            res += do_it;
        }
        mp[target] = res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/338703