Non-contiguous element divisible by n solution not working

Question

What is an efficient way to count the number of non contiguous sub-sequences of a given array of integers divisible by n? A = {1,2,3,2} n = 6 Output 3 because 12, 12, 132 are divisible by 6

My solution which uses dynamic programming is giving me wrong result. It is always giving me one more than the actual result.

#include <stdio.h>

#define MAXLEN 100
#define MAXN 100
int len = 1,ar[] = {1, 6, 2},dp[MAXLEN][MAXN],n=6;

int fun(int idx,int m)
{
    if (idx >= (sizeof(ar)/sizeof(ar[0])))
        return m == 0;
    if(dp[idx][m]!=-1)
        return dp[idx][m];
    int ans=fun(idx+1,m);                // skip this element in current sub-sequence
    ans+=fun(idx+1,(m*10+ar[idx])%n);    // Include this element. Find the new modulo by 'n' and pass it recursively
    return dp[idx][m]=ans;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    printf("%d\n",fun(0, 0));            // initially we begin by considering array of length 1 i.e. upto index 0
    return 0;
}

Can anyone point out the mistake?

Answer 1

The problem is that the "empty" sequence is considered a solution (m == 0 when you start the call and not adding any digit will leave you with m == 0 at the end).

Either that is correct but then the solution for {1, 2, 3, 2} is 4, or you need to subtract it by just giving as reply fun(0, 0)-1.