-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathCoinChange.java
More file actions
37 lines (34 loc) · 1002 Bytes
/
CoinChange.java
File metadata and controls
37 lines (34 loc) · 1002 Bytes
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
import java.util.ArrayList;
import java.util.Collections;
/**
* Created by Devang on 7/12/2017.
*/
public class CoinChange {
public static void main(String[] args) {
// int n = 5;
ArrayList<Integer> s = new ArrayList<>();
s.add(1);
s.add(5);
s.add(10);
s.add(20);
s.add(50);
s.add(100);
System.out.println(CoinChange(7, s));
System.out.println(CoinChange(17, s));
System.out.println(CoinChange(23, s));
System.out.println(CoinChange(8, s));
System.out.println(CoinChange(5, s));
}
public static int CoinChange(int n, ArrayList<Integer> s) {
ArrayList<Integer> result = new ArrayList<>();
if (s.contains(n)) {
return 1;
}
for (int i = 0; i < s.size(); i++) {
if(s.get(i) <= n){
result.add( (CoinChange(n - s.get(i), s)));
}
}
return Collections.min(result) + 1;
}
}