algorithm - 子集计数问题，如何调试解决方案不起作用的地方？

Question

所以我试图解决这个问题：

给定一个整数数组 arr[] 和一个整数和，任务是计算给定数组的所有子集，其总和等于给定总和。

注意：答案可能非常大，因此，输出答案模 10^9+7

现在这是我在这里尝试的解决方案：

class Solution{
    private:
    vector<vector<int>> t;
    public:
    Solution() {
        t.resize(1001, vector<int> (1001,-1));
    }
    int perfectSum(int arr[], int n, int sum)
    {  
        long long int result = fmod(sumrecursive(arr, n, sum),(pow(10,9)+7));
        return result;
    }
    
    long long int sumrecursive(int arr[], int n, int sum){
        
        if(sum==0){
            return 1;
        } 
        if(n==0){
            return 0;
        }
        
        if(t[n][sum] != -1){
            return t[n][sum];
        }
        
        if(arr[n-1]>sum){
            return t[n][sum] = sumrecursive(arr, n-1, sum);
        } else {
            return t[n][sum] = sumrecursive(arr,n-1, sum-arr[n-1]) + sumrecursive(arr, n-1, sum);
        }
    }
      
};

现在此代码在某些输入后不起作用：

在这一点上，我不知道如何着手解决这个问题。理想情况下，根据我编写的代码，输入在代码的掌握范围内，输出应该是正确的，但不幸的是事实并非如此。我想问是否有人可以发现代码中的问题所在，或者指导我如何调试代码中的问题所在。

标签： algorithmrecursiondynamic-programming

Answer 1

您可能会在此过程中遇到整数溢出。

您只是在结束函数之前使用 mod，但是您的缓存是 type int，所以当放置太大的数字时 - 由于溢出，您会丢失一些数据。