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

Cho một mảng nguyên dương với các phần tử duy nhất, hãy tìm số lượng tổ hợp có thể có sao cho tổng của chúng bằng một số nguyên dương target cho trước.

Ví dụ, nếu mảng là [1, 2, 3] và target là 4, các tổ hợp khả thi là [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2, 2]], nên đầu ra là 7.

Để giải quyết, ta sử dụng đệ quy có nhớ (dynamic programming):

• Định nghĩa hàm solve() nhận mảng, target và mảng dp. Quy trình:
  • Nếu target = 0, trả về 1
  • Nếu dp[target] ≠ -1, trả về dp[target]
  • ans := 0
  • Với i từ 0 đến nums.size()-1:
    • Nếu target ≥ nums[i], ans := ans + solve(nums, target - nums[i], dp)
  • Đặt dp[target] := ans
  • Trả về ans

Ví dụ (C++):

Xem 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; 
    } 
}; 

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

Đầu vào

[1,2,3] 4

Đầu ra

7