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()，该函数将数组，目标和另一个数组用于动态编程任务。这个过程会像
如果target=0，则返回1
如果dp[target]不为-1，则返回dp[target]
回答：=0
对于我，范围从0到nums
ans：=ans+solve（nums，target–nums[i]，dp）
如果目标>=nums[i]
设置dp[target]：=ans
返回ans
例子（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