Pinky and The Brain are great friends. They like to play games with numbers. This time, Pinky has given The Brain a list of numbers and given him the task of determining if it is possible to choose a subset of them such that they sum is equal to another given number.
Build an algorithm using dynamic programming to help The Brain with his problem.
INPUT
OUTPUT
Sample Input 1:
39
15
88
3
43
40
100
45
34
89
10
17
70
14
63
92
24
64
6
42
12
81
34
38
63
35
77
67
80
5
58
46
17
67
21
73
10
49
21
54
128
Sample Output 1:
True
Sample Input 2:
30
72
21
33
6
72
53
71
28
66
92
90
73
33
10
70
25
96
82
85
53
58
61
76
20
85
4
1
7
34
76
670
Sample Output 2:
True
Sample Input 3:
35
8
63
89
6
83
78
31
5
46
95
59
73
98
47
43
16
44
50
32
5
77
23
30
44
69
94
24
14
50
99
82
90
1
21
25
557
Sample Output 3:
True
Sample Input 4:
38
2
24
70
51
24
51
98
9
81
55
11
50
94
42
91
94
8
64
86
20
25
34
100
65
30
49
99
47
63
20
3
61
5
100
86
22
94
60
1766
Sample Output 4:
True
Sample Input 5:
21
29
53
31
74
21
57
35
67
10
86
60
46
17
52
38
21
14
51
26
12
86
647
Sample Output 5:
True
Write a program, test using stdin → stdout
import java.util.*;
public class Solution {
static boolean checkSubset(int[] arr, int n, int sum)
{
boolean mat[][] = new boolean[sum + 1][n + 1];
for (int i = 0; i <= n; i++)
mat[0][i] = true;
for (int i = 1; i <= sum; i++)
mat[i][0] = false;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
mat[i][j] = mat[i][j - 1];
if (i >= arr[j - 1])
mat[i][j] = mat[i][j] || mat[i - arr[j - 1]][j - 1];
}
}
return mat[sum][n]; }
public static void main(String[] args) {
int n;
int[] arr;
int sum;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
sum = scanner.nextInt();
System.out.print(checkSubset(arr, n, sum));
scanner.close();
}
}
Hi,If you like the solution please press the thumb up button.
Get Answers For Free
Most questions answered within 1 hours.