leetcode 377. 组合总和 Ⅳ

秒速五厘米 2023-07-03 08:17 8阅读 0赞

### 解题思路 ###

完全背包计数的思路就不写了，因为这只要了解背包，就可以直接打出来了。  
这题用c++写，必须用unsigned long long 来存储。数据量很大。  
这里提一下完全背包的写法。其实这个题有点特殊，顺序不同的组合也要算一组，所以枚举的顺序必须是  
for(int j=1;j<=target;j++)  
for(int i=0;i<n;i++)

倘若没有顺序要求即(1,2,1)和(1,1,2)是一样的话。就要反过来写。

### 代码 ###

class Solution { 
    public:
        int combinationSum4(vector<int>& nums, int target) { 
            int n=nums.size();
            int dp[target+3];
            unsigned long long f[target+3];
            memset(dp,0,sizeof(dp));
            memset(f,0,sizeof(f));
            f[0]=1;
            for(int j=1;j<=target;j++)
            { 
                for(int i=0;i<n;i++)
                { 
                    if(j<nums[i]) continue;
                    if(dp[j-nums[i]]+nums[i]>=dp[j])
                    { 
                        dp[j]=dp[j-nums[i]]+nums[i];
                        f[j]+=f[j-nums[i]];
                        //cout<<j<<" "<<dp[j]<<" "<<f[j]<<endl;
                    }
                }
            }
           // cout<<dp[target]<<endl;
            return f[target];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 377. 组合总和 Ⅳ ——【Leetcode每日一题】

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

分手后的思念是犯贱/ 2024年03月25日 20:00/ 0 赞/ 28 阅读

相关 LeetCode-377. 组合总和 Ⅳ

题目来源 [377. 组合总和 Ⅳ][377. _] 题目分析本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！可以做下

蔚落/ 2024年03月25日 16:51/ 0 赞/ 54 阅读

相关 377. 组合总和 Ⅳ

377. 组合总和 Ⅳ 题干描述解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如何初

待我称王封你为后i/ 2023年10月16日 16:49/ 0 赞/ 15 阅读

相关 leetcode 377. 组合总和 Ⅳ

解题思路完全背包计数的思路就不写了，因为这只要了解背包，就可以直接打出来了。这题用c++写，必须用unsigned long long 来存储。数据量很大。

秒速五厘米/ 2023年07月03日 08:17/ 0 赞/ 9 阅读

相关 377. 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例: nums = \[1, 2, 3\] target = 4 所有可能的组合为

古城微笑少年丶/ 2022年11月29日 11:47/ 0 赞/ 128 阅读

相关 Leetcode 39. 组合总和

题目重述给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一

旧城等待，/ 2022年09月09日 04:36/ 0 赞/ 223 阅读

相关 leetcode 377. Combination Sum IV | 377. 组合总和 Ⅳ（动态规划）

题目 [https://leetcode.com/problems/combination-sum-iv/][https_leetcode.com_problems_co

喜欢ヅ旅行/ 2022年08月29日 12:56/ 0 赞/ 146 阅读

相关 LeetCode 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例: nums = [1, 2, 3] target = 4

ゞ浴缸里的玫瑰/ 2022年04月08日 09:47/ 0 赞/ 236 阅读

相关【leetcode】组合总和 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2022年03月11日 10:10/ 0 赞/ 251 阅读

相关 LeetCode-39.组合总和

题目给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candi

╰+哭是因爲堅強的太久メ/ 2022年01月27日 15:37/ 0 赞/ 265 阅读