### Can anybody help me out?

Given an array of n integers, we need to find no of subsets of size k where sum of elements in each choosen subset is divisible by m.

 ``12345678910111213141516171819202122232425262728`` `````` n,m,k =>3,3,2 Array:[1,2,3] Output: 1 Because there is only 1 subset of size k divsible by m {1,2} My function looks like: void combinationUtil(int arr[], int n, int k, int index,int data[], int i,int m) { if (index == k) { int sum=0; for (int j = 0; j < k; j++) sum=sum+data[j]; if(sum%m==0) { cnt=(cnt%MOD+1)%MOD; } return; } if (i >= n) return; data[index] = arr[i]; combinationUtil(arr, n, k, index + 1, data, i + 1,m); combinationUtil(arr, n, k, index, data, i + 1,m); }``````

Can somebody suggest better idea, how to tackle this problem ?
Last edited on
Some questions:
- What are "cnt", "MOD" and "data" here?
- What does your code look like when you are going to run it (including main function and includes and preferably comments)?
- Will "k" always be 2?
- How did you get to this point?
@Nico Sorry for inconvenience.

cnt and MOD are defined globally

cnt= Count of subsets whose sum is divisble by m.
MOD=10^9+7

data is array to storethe elements of subsets.

K=It can be of any size. (k<=n)

My code is doing following things:

Array:[1,2,3]

I am checking every subset of size k=2. m=3

[1,2]=3%m==0
[2,3]=5%m !=0
[1,3]=4%m!=0

So there is only 1 subset of size k whose sum is divisible by m.

So cnt=1

This function will be called in following manner

combinationUtil(arr,n,k,0,data,0,m)
Last edited on