Repository navigation
Expand file tree
/
Copy pathtarget.java
More file actions
45 lines (40 loc) · 1.42 KB
/
Copy pathtarget.java
File metadata and controls
45 lines (40 loc) · 1.42 KB
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
import java.util.HashMap;
public class target {
public static void main(String[] args) {
System.out.println(Cansum(7, new int[] { 2, 4 },new HashMap<>()));
System.out.println(Cansum(7, new int[] { 2, 3, 5 },new HashMap<>()));
System.out.println(Cansum(7, new int[] { 5, 7, 4, 3 },new HashMap<>()));
System.out.println(Cansum(300, new int[]{7,14}, new HashMap<>()));
}
private static boolean Cansum(int targetsum, int[] numbers, HashMap<Integer,Boolean> hashMap) {
if (targetsum == 0)
return true;
if (targetsum < 0)
return false;
if (hashMap.containsKey(targetsum)) {
return hashMap.get(targetsum);
}
for (int i : numbers) {
int remainder=targetsum-i;
if (Cansum(remainder, numbers, hashMap)==true) {
hashMap.put(targetsum, true);
return true;
}
}
hashMap.put(targetsum, false);
return false;
}
// private static boolean Cansum(int targetsum, int[] numbers) {
// if (targetsum == 0)
// return true;
// if (targetsum < 0)
// return false;
// for (int i : numbers) {
// int remainder = targetsum - i;
// if (Cansum(remainder, numbers) == true) {
// return true;
// }
// }
// return false;
// }
}