Non-contiguous element divisible by n-solution does not work

Question

What is an effective way of counting the number of disjoint subsequences of a given array of integers divisible by n? A = {1,2,3,2} n = 6 Conclusion 3 because 12, 12, 132 are divided by 6

My solution using dynamic programming gives me the wrong result. It always gives me 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 ie upto index 0 return 0; } 

Can anyone point out an error?

Answer 1

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

Is this correct, but then the solution for {1, 2, 3, 2} is 4, or do you need to subtract it by simply specifying fun(0, 0)-1 as the answer.