Question

Pinky and The Brain are great friends. They like to play games with numbers. This time,...

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

• The first line corresponds to N, the amount of numbers given by Pinky
• The next N lines contain each of the numbers
• The last line contains the desired sum

OUTPUT

• True or False (Whether is possible to obtain the desired sum or not)

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.