I am working on the following problem:

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N and M where N denotes the size of the array and M is the number for which we have to check the divisibility. The second line of each test case contains N space separated integers denoting elements of the array A[ ].

Output: If there is a subset which is divisible by M print '1' else print '0'.

I have tried a recursive solution:

#include <iostream>

#include<unordered_map>

using namespace std;



bool find_it(int a,int &m,int n,int sum) {

    if ((sum%m)==0 && sum>0)

        return true;

    if (n==0)

        return false;

    return find_it(a,m,n-1,sum) || find_it(a,m,n-1,sum-a[n-1]);

}



int main() {

    int tc;

    cin >> tc;

    while (tc--) {

        int n,m;

        cin >> n >> m;

        int a[n];

        int sum = 0;

        for (int i=0;i<n;i++) {

            cin >> a[i];

            sum += a[i];

        }

        bool answer = find_it(a,m,n,sum);

        cout << answer << "n";

    }

   return 0;

}

Which works fine and get accepted, but then I tried top-down approach, and am getting TLE ("Time Limit Exceeded"). What am I doing wrong in this memoization?

#include <iostream>

#include<unordered_map>

using namespace std;



bool find_it(

    int a, int &m, int n, int sum,

    unordered_map<int,unordered_map<int,bool>> &value,

    unordered_map<int,unordered_map<int,bool>> &visited){



    if ((sum%m)==0 && sum>0)

        return true;

    if(n==0)

        return false;



    if(visited[n][sum]==true)

        return value[n][sum];



    bool first = false,second = false;

    first = find_it(a,m,n-1,su1m,value,visited);



    if(sum<a[n-1])

    {

        second=false;

    }

    else

    second = find_it(a,m,n-1,sum-a[n-1],value,visited);



    visited[n][sum] = true;

    value[n][sum] = first || second;

    return value[n][sum];

}



int main() {

    int tc;

    cin >> tc;

    while (tc--) {

        int n,m;

        cin >> n >> m;

        int a[n];

        int sum = 0;

        for (int i=0;i<n;i++) {

            cin >> a[i];

            sum+=a[i];

        }

        unordered_map<int,unordered_map<int,bool>> value;

        unordered_map<int,unordered_map<int,bool>> visited;

        cout << find_it(a,m,n,sum,value,visited) << "n";

    }

    return 0;

}

There is no need for value. Once you find a valid combination, i.e. if find_it ever returns true, you can just immediately return true in all recursive calls.

Some additional remarks:

1. You should use consistent indentation.


2. Variable sized arrays as in int a[n] are not standard C++ and will not work on all compilers.


3. There is no reason to pass m as int& instead of int.


4. A map taking boolean values is the same as a set where the element is assumed to map to true if it is in the set and false if it is not. Consider using unordered_set instead of unordered_map.


5. Composing two unordered_maps like this is expensive. You can just as easily put both keys into a std::pair and use that as key. This would avoid the overhead of maintaining the map.


6. 
   bits/stdc++.h is also non-standard and you should specify the correct header files instead, e.g. #include <unordered_map> and #include <iostream>.


7. You should put spaces between the variable type and its name, even if the > from the template parameter allows it to parse correctly without. It makes code hard to read.

Well, at first, you can reduce the problem to a modulo m problem, as properties of integers don't change when switching to modulo m field. It's easy to demonstrate that being divisible by m is the same as being identical to 0 mod m.

I would first convert all those numbers to their counterparts modulo m and eliminate repetitions by considering a_i, 2*a_i, 3*a_i,... until rep_a_i * a_i, all of them mod m. Finally you get a reduced set that has at most m elements. Then eliminate all the zeros there, as they don't contribute to the sum. This is important for two reasons:

• It converts your problem from a Knapsack problem (NP-complete) on which complexity is O(a^n) into a O(K) problem, as its complexity doesn't depend on the number of elements of the set, but the number m.


• You can still have a large set of numbers to compute. You can consider the reduced set a Knapsack problem and try to check (and further reduce it) for an easy-knapsack problem (the one in which the different values a_i follow a geometric sequence with K > 2)

The rest of the problem is a Knapsack problem (which is NP-complete) or one of it's P variants.

In case you don't get so far (cannot reduce it to an easy-knapsack problem) then you have to reduce the number of a_i's so the exponential time gets a minimum exponent :)

edit

(@mss asks for elaboration in a comment) Assume you have m = 8 and the list is 1 2 4 6 12 14 22. After reduction mod m the list remains as: 1 2 4 6 4 6 6 in which 6 is repeated three times. we must consider the three possible repetitions of 6, as they can contribute to get a sum, but not more (for the moment), let's consider 6*1 = 6, 6*2 = 12 and 6*3 = 18, the first is the original 6, the second makes a third repetition of 4 (so we'll need to consider 3 4s in the list), and the third converts into a 2. So now, we have 1 2 4 6 4 4 2 in the list. We make the same for the 4 repetitions (two 4 run into 8 which is 0mod m and don't contribute to sums, but we have to keep one such 0 because this means you got by repeated numbers the target m) getting into 1 2 4 6 0 4 2 => 1 2 4 6 0 0 2 =(reorder)=> 0 1 2 2 4 6 => 0 1 2 4 6. This should be the final list to consider. As it has a 0, you know a priori that there's one such sum (in this case you got is as including the two 4, for the original list's 4 and 12 numbers.