Reduce subsequence problem complexity from exponential to polynomial?

Question

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

Answer 1

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.

Answer 2

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.