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

Question

所以我正在尝试解决 this problem :

Given an array arr[] of integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.

Note: Answer can be very large, so, output answer modulo 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);
        }
    }
      
};

现在这段代码在某些特定输入后不起作用：

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

Answer 1

你可能正在路上遇到integer overflow。

您仅在函数结束前使用 mod，但您的缓存类型为 int，因此当放置太大的数字时 - 您会因溢出而丢失一些数据。

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

Count of subsetsum problem, how to debug where the solution is not working?

algorithm

recursion

dynamic-programming