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