資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學科
時尚學科
法律學科C++ 中的組合總和 IV
假設我們有一個整數陣列，其中所有正數元素都是唯一的，求出可能組合的數量，如果相加，將得到正整數目標。
因此，如果陣列為 [1, 2, 3]，目標為 4，可能的組合包括 [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2, 2]]，因此輸出為 7。
要解決此問題，我們將按照下列步驟操作 -
- 假設我們有一個稱為 solve() 的遞迴函式，它獲取動態程式設計任務的陣列、目標和另一個數組。該過程如下：
- 如果目標 = 0，則返回 1
- 如果 dp[目標] 不為 -1，則返回 dp[目標]
- 答案：= 0
- 對於範圍 0 到數字的 i
- 如果目標 >= 數字[i]
- 答案：= 答案 + solve(數字，目標 – 數字[i]，dp)
- 如果目標 >= 數字[i]
- 設定 dp[目標] := 答案
- 返回答案
示例（C++）
讓我們看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector <int> dp(target + 1, -1);
return helper(nums, target, dp);
}
int helper(vector <int>& nums, int target, vector <int>& dp){
if(target == 0)return 1;
if(dp[target] != -1)return dp[target];
int ans = 0;
for(int i = 0; i < nums.size(); i++){
if(target >= nums[i]){
ans += helper(nums, target - nums[i], dp);
}
}
return dp[target] = ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3};
cout << ob.combinationSum4(v, 4);
}輸入
[1,2,3] 4
輸出
7
更新時間：2020 年 4 月 28 日
瀏覽量 208
廣告