一:題目

二:上碼

1:動(dòng)態(tài)規(guī)劃

class Solution { public:/**思路:1.首先確定完全背包 因?yàn)槲覀兛梢灾貜?fù)加入2.動(dòng)態(tài)規(guī)劃5步走1>:確定dp數(shù)組以及下標(biāo)的含義dp[i] 表示的是背包容量為i的時(shí)候(這里的 i 也是就是我們的target),有多少種排列數(shù)目2>:確定dp數(shù)組的遞推公式這個(gè)是統(tǒng)計(jì)有多少種 排列的個(gè)數(shù),所以我們是需要用到前面求出來的結(jié)果比如 i = 5 的時(shí)候，這時(shí)放入背包的是 2 那么我們是需要dp[3]的排列結(jié)果的3>:確定dp數(shù)組的初始化dp[0] = 1;4>:確定dp數(shù)組的遍歷順序如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包。如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。5>:*/int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1,0);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_MAX - dp[i - nums[j]])//這里需要判斷的是防止兩個(gè)數(shù)的和超過最大值dp[i] += dp[i-nums[j]]; //即dp[i] + dp[i-nums[i]] < INT_MAX} }return dp[target];} };

2：回溯暴搜（超時(shí)）

記錄失敗碼

class Solution { public:/**思路:1.確定好回溯函數(shù)的返回值和參數(shù)2.確定好回溯函數(shù)的遞歸終止條件3.確定遍歷順序*/vector<vector<int> > ans;vector<int> path;void backstacking(vector<int>& nums,int target,int sum) {// int sum = accumulate(path.begin(),path.end(),0);if(sum >= target) {if(sum == target) ans.push_back(path);return;}for(int i = 0; i < nums.size(); i++) {path.push_back(nums[i]);sum+=nums[i];backstacking(nums,target,sum);path.pop_back();sum-=nums[i];}}int combinationSum4(vector<int>& nums, int target) {backstacking(nums,target,0);return ans.size();} };

總結(jié)

以上是生活随笔為你收集整理的leetcode377. 组合总和 Ⅳ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。