Tổng kết hợp IV trong C ++

Giả sử chúng ta có một mảng số nguyên với tất cả các số dương và tất cả các phần tử là duy nhất, hãy tìm số lượng các kết hợp có thể có, để nếu chúng ta cộng lại, chúng ta sẽ nhận được mục tiêu là số nguyên dương.

Vì vậy, nếu mảng là [1, 2, 3] và đích là 4, thì các kết hợp có thể có sẽ là [[1,1,1,1], [1,1,2], [1,2,1] , [2,1,1], [1,3], [3,1], [2, 2]], vì vậy đầu ra sẽ là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Giả sử chúng ta có một hàm đệ quy được gọi là giải quyết (), hàm này lấy mảng, đích và một mảng khác cho các tác vụ lập trình động. Quá trình sẽ như thế nào
• nếu target =0, thì trả về 1
• nếu dp [target] không phải là -1, thì trả về dp [target]
• ans:=0
• cho tôi trong phạm vi từ 0 đến nums
  • if target> =nums [i]
    • ans:=ans + giải quyết (nums, target - nums [i], dp)
• đặt dp [target]:=ans
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[1,2,3]
4

Đầu ra

7