forked from hrsvrdhn/DP
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SubsetSumDivisibleByM
93 lines (76 loc) · 2.81 KB
/
SubsetSumDivisibleByM
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//Java program to find a subset with sum divisible by m
import java.util.Arrays;
class DP {
// Returns true if there is a subset
// of arr[] with sum divisible by m
static boolean modularSum(int arr[],
int n, int m)
{
if (n > m)
return true;
// This array will keep track of all
// the possible sum (after modulo m)
// which can be made using subsets of arr[]
// initialising boolean array with all false
boolean DP[]=new boolean[m];
Arrays.fill(DP, false);
// we'll loop through all the elements
// of arr[]
for (int i = 0; i < n; i++)
{
// anytime we encounter a sum divisible
// by m, we are done
if (DP[0])
return true;
// To store all the new encountered sum
// (after modulo). It is used to make
// sure that arr[i] is added only to
// those entries for which DP[j]
// was true before current iteration.
boolean temp[] = new boolean[m];
Arrays.fill(temp, false);
// For each element of arr[], we loop
// through all elements of DP table
// from 1 to m and we add current
// element i. e., arr[i] to all those
// elements which are true in DP table
for (int j = 0; j < m; j++)
{
// if an element is true in
// DP table
if (DP[j] == true)
{
if (DP[(j + arr[i]) % m] == false)
// We update it in temp and update
// to DP once loop of j is over
temp[(j + arr[i]) % m] = true;
}
}
// Updating all the elements of temp
// to DP table since iteration over
// j is over
for (int j = 0; j < m; j++)
if (temp[j])
DP[j] = true;
// Also since arr[i] is a single
// element subset, arr[i]%m is one
// of the possible sum
DP[arr[i] % m] = true;
}
return DP[0];
}
//driver code
public static void main(String arg[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i]= sc.nextInt();
if(modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}