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.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  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
Registered users can post here. Sign in or register to post.