Combination Sum IV ใน C++

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

ตัวอย่างเช่น หากอาร์เรย์คือ [1, 2, 3] และ target คือ 4 การจัดหมู่ที่เป็นไปได้จะเป็น [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2, 2]] ดังนั้นผลลัพธ์คือ 7

ขั้นตอนการแก้ปัญหา

• สมมติว่ามีฟังก์ชันเวียนเกิดชื่อ solve() ซึ่งรับพารามิเตอร์เป็นอาร์เรย์, target และอีกอาร์เรย์หนึ่งสำหรับ dynamic programming กระบวนการจะเป็นดังนี้
• ถ้า target = 0 ให้คืนค่า 1
• ถ้า dp[target] ไม่ใช่ -1 ให้คืนค่า dp[target]
• ans := 0
• for i ในช่วง 0 ถึง nums
  • ถ้า target >= nums[i]
    • ans := ans + solve(nums, target - nums[i], dp)
• ตั้งค่า 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; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,2,3}; 
    cout << ob.combinationSum4(v, 4); 
}

อินพุต

[1,2,3] 4

เอาต์พุต

7