CODEWITHSUNDEEP
algorithmdynamic-programming
shubham jha
shubham jha

Reputation: 1480

how to count all possible subsets that's elements adds up to a given number with duplicates elements

I have given some numbers say {a,b,c,d},I can use these numbers any number of times to make sum 'N'. I have to calculate all possible combination let's say it 'A' and i have to return A%M where M is some large prime number. constraint that causing problem to me is N <= 10^18. Size of set {a,b,c,d..} is less tha equal to 100.

I am using dynamic programming to solve it but the problem is i can't use 10^18 size array and if i am not caching precomputed values then time limit get exceeded.

    #define M 1000000007
    long long solve(long long N, vector<long long>& v, vector<long long>& dp){
        if(N==0){
           return 1;
         }
         if(dp[N]!=-1){
               return dp[N];  
          }
         int n = v.size(); // maximum size of v <=100
         long long ans = 0;
         for(int i=0;i<n;i++){
                 if(N-v[i]>=0){
                     ans = (ans + solve(N-v[i],v,dp))%M; 
                  }
            }
          dp[N] = ans;
          return ans;

     }
    int main(){

        long long n, N;   // n: size of set , N: expected sum
        cin>>n>>N;
        vector<long long>v(n);
        for(int i=0;i<n;i++){
             cin>>v[i];
         }
        long long ans  = 0;
        vector<long long>dp(N+1,-1);
        for(int i = 0;i<n;i++){
                if(N-v[i]>=0){
                     ans = (ans + solve(N-v[i],v,dp))%M; 
                  }
           }
        cout<<ans<<endl;
     }

how to optimize this to handle sum 10^18 without exhausting time.

Upvotes: 0

Views: 114

Answers (1)

btilly
btilly

Reputation: 46507

For the sake of an example I'll assume that your set is {1, 1, 3} and we want to calculate the 100th term. But the approach will work in general.

Let k be the maximum of your set. Let's let s[i] be the number of ways to make i as a sum. Our starting condition is s[-k+1] = 0, s[-k+2]= 0, ..., s[-1] = 0 but s[0] = 1. Our induction step for {a, b, c, ...} is s[n] = s[n-a] + s[n-b] + s[n-c] + ....

But now reconceptualize it. Consider the vector v[n] = (s[n-k+1], s[n-k+2], ... + s[n]). Let A[m] be the matrix that you have to multiply by to get the vector v[n+m] = (s[n+m-k+1], s[n+m-k+2], ..., s[n+m]). I will assume that it exists. The usual proof for the Fibonacci sequence generalizes if you want to work it out.

Now there are two facts about these matrices that we need.

The first is that A[m1 + m2] = A[m1] * A[m2]. To see that just note that for all n, (A[m1] * A[m2])(v[n]) = A[m1]( A[m2]( v[n] ) ) = A[m1]( v[n + m2] ) = v[n + m2 + m1] = A[m1 + m2]( v[n] ).

The second is that we can compute A[1] very easily. It has all 1's on the upper diagonal, followed by a last row that has +1 wherever there is something in our set. (Or a +2 if the element is in our set twice, as I made sure was true in our example.) So for our example we have:

[0 1 0]   [ v[n-2] ]   [ v[n-1] ]
[0 0 1] * [ v[n-1] ] = [ v[n]   ]
[1 0 2]   [ v[n]   ]   [ v[n+1] ]

And the initial matrix is A[1].

Now suppose that we want to calculate s[100]. That is the last entry of v[100]. But now we proceed down by halving as follows: A[100] = A[50] * A[50]. A[50] = A[25] * A[25]. A[25] = A[12] * A[13]. A[13] = A[1] * A[12]. A[12] = A[6] * A[6]. A[6] = A[3] * A[3]. A[3] = A[2] * A[1]. And finally, A[2] = A[1] * A[1]. But we have A[1] and this gives us A[100] after 8 matrix multiplies. Since everything is growing exponentially, the theoretical answer has absurdly large integers, but those operations are easy to do mod p.

Is this doable? If n = 10**18 we have at most around 60 halving, each of which could with this naive approach have another +1 multiply for 120 matrix operations. If the largest element of the set is 100, that is around 2 million per matrix multiply (half multiplications, half additions), for 240 million operations.

You still have a lot of work ahead of you. But with this matrix approach, it is at least doable.

Upvotes: 2

Related Questions