# Count Of Subsets With Given Difference between subsets - Coding Interview Question Mani
Educating everyone with the beauty of programming!!

Given an array of integers. Count the number of subsets whose difference between pair of subsets is equals to given difference.

Example 1:

int[] a = {1,1,2,3} difference = 1

Output: 3

Explanation: Possible choices are
1. {1, 3} , {1 , 2}
2. {1, 3} , {1 , 2} : Since there are duplicates in input.
3. {1,1,2} , {3}

Solution:

``````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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Arrays;

public class CountOfSubsetsWithGivenDifferencebetweensubsets {

public static void main(String[] args) {
int[] a = {1, 1, 2, 3};
int diff = 1;
System.out.println(countSubsetsWithDiff(a, diff));
}

static int countSubsetsWithDiff(int[] a, int diff) {
int sum = 0;
for (int i : a) {
sum += i;
}
int c = (diff + sum);
if (c % 2 == 1) {
return 0;
}
c = c / 2;

int[][] dp = new int[c + 1][a.length + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp.length; j++) {
if (i == 0) {
dp[i][j] = 1;
continue;
}

if (j == 0) {
continue;
}

if (a[j - 1] <= i) {
dp[i][j] = dp[i - a[j - 1]][j - 1] + dp[i][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}

//        for(int[] d : dp) {
//            System.out.println(Arrays.toString(d));
//        }

return dp[c][a.length];
}

}
``````
Drop your comments below for any questions or comments. For full list of must learn top interview questions Click Here: Must Learn Top Interview Questions

Rating: