รวมผลรวม IV ใน C ++

สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่มีจำนวนบวกทั้งหมดและองค์ประกอบทั้งหมดไม่ซ้ำกัน ค้นหาจำนวนชุดค่าผสมที่เป็นไปได้ เพื่อที่ว่าถ้าเรารวมกัน เราจะได้เป้าหมายจำนวนเต็มบวก

ดังนั้นหากอาร์เรย์คือ [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[target] ไม่ใช่ -1 ให้ส่งคืน dp[target]
• ตอบ :=0
• สำหรับฉันอยู่ในช่วง 0 ถึง nums
  • ถ้าเป้าหมาย>=nums[i]
    • ans :=ans + แก้ (nums, เป้าหมาย – nums[i], dp)
• set dp[target] :=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