数据结构
网络
关系型数据库管理系统
操作系统
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
广告